Anhand des Projekts word-dist habe ich am 10. Dezember 2020 bei der LUG-Jena in einem Vortrag die Arbeitsweise und Programmierung in Rust erläutern. Der Mitschnitt ist leider nicht sehr gut geworden, aber er ist noch verständlich. Hintergrund dazu gibt es unter »Nachbearbeitung der BigBlueButton-Aufzeichnung«.

Problemstellung

Viele Stichworte meiner Webseite ähneln sich

  • Referenz*en* ⟷ Referenz
  • V*lc* ⟷ VLC
  • Ope*nS*ource ⟷ Open-Source
  • Quelle/Zeit ⟷ Quelle/Zeit.de ⟷ Quelle/Zeit-Online

Idee

Ähnlichkeit von Worten berechnen. »Da gab es irgendwas mit Hamming-Abstand«.

Umsetzung

Recherche bei crates.io

  • Für Rust gibt es eigene Pakete (crates) mit den Bibliotheken, so wie npm oder gem.
  • Suche bei crates.io nach »Hamming«
  • strsim klingt gut, Levenshtein habe ich auch schonmal gehört 🙂

Neues Projekt anlegen

  • Rust hat das Programm cargo für die Verwaltung von Projekten erfunden. Die Syntax ähnelt der von git/svn. The Cargo Book
  • cargo new word-dist; es gibt zwei Typen von Projekten: Programme (bin) und Bibliotheken (lib); default ist bin
  • cargo erzeugt immer ein git mit; kann man auch unterbinden bzw. innerhalb eines bestehenden gits, macht es das nicht
  • Projekte haben eine recht starre Struktur: benches, examples, src, target, tests; Package Layout
    • Anmerkung zu target: dort landet das erstellte Programm und alle Zwischendateien; dieses Verzeichnis kann riesig werden; vom Backup ausschließen
    • Anmerkung²: ähnlich auch ~/.cargo/(git|registry)/, nur noch größer
  • die Projektdatei ist Cargo.toml; Syntax ähnlich ini-Dateien, aber im Detail etwas anders; The Manifest Format
  • Cargo.toml bearbeiten:
    • description = "Computes the pairwise similarity between multiple words"
    • license = "GPL-3.0-or-later" SPDX License List
    • keywords = ["word", "string", "similarity", "distance", "Hamming", "Levenshtein", "Jaro"]
    • categories = ["command-line-utilities"]
    • repository = "https://gitlab.com/jo-so/word-dist"
  • Datei LICENSE hinzufügen

strsim einbinden

  • cargo lässt sich (wie auch git) mit Paketen erweitern. Man kann diese mit cargo install cargo-edit installieren
  • Hinzufügen (und entfernen) von Bibliotheken geht mit cargo-edit sehr angenehm: cargo add strsim
  • jetzt wurde die Datei Cargo.lock angelegt: Cargo.toml vs. Cargo.lock
  • Programme haben ihren Anfang immer in src/main.rs. Dort ist (i. d. R.) die fn main() zu finden.
  • Beispiel-Code von strsim einfügen; extern crate strsim; nicht mehr notwendig seit einigen Versionen.
  • Projekte übersetzen geht mit cargo build
  • Projekte ausführen geht mit cargo run bzw. cargo r
  • cargo kennt Aliase; ~/.cargo/config

    [alias]
    b = "build --tests"
    br = "build --release"
    
  • Ich verwende den Shell-Alias alias c=cargo; damit c r

Paare von Wörtern bilden

  1. Variablendefinition in Rust mit let var = 42; Variablen sind immer nur einmalig zuweisbar; veränderbare Variablen muss man mit let mut name = … anlegen. Rust ist an kritischen Punkten explizit: Wenn man etwas haben will, muss man es sagen
  2. Variablen muss man keinen (oder fast nie einen) Typ angeben. Rust ermittelt ihn selbst anhand der ersten Verwendung. Sollte dies zu Konflikten führen, meckert der Compiler und ggf. muss man ihm helfen.
  3. Rust hat eine for-each-Schleife:

     fn main() {
         let words = vec!["Wort 1", "Wort 2", "Wort 3"];
     
         for w in words {
             println!("{}", w);
         }
     }
    
  4. Ausführen mit c r

  5. Am Ende soll jedes Wort mit jedem verglichen werden:

     for w1 in words {
         for w2 in words {
             println!("{} {}", w1, w2);
         }
     }
    
  6. Fehler: eine for-Schleife iteriert über eine Menge mithilfe eines Iterators (Abstraktion, um über alle möglichen Mengen iterieren zu können). Für die erste for-Schleife wird words implizit in einen Iterator umgewandelt und verbraucht. Daher steht words für die zweite Schleife nicht mehr zur Verfügung. Die Umwandlung erfolgt mit der Methode into_iter().

  7. Lösung: einfach nur einen Verweis auf die Menge übergeben (der implizit konvertiert wird) for w1 in &words {
  8. neuer Fehler: die innere Schleife verbraucht words (durch into_iter()) im ersten Durchlauf der äußeren Schleife, weshalb &words im zweiten Durchlauf nicht mehr verfügbar ist. – Am besten malt man sich das auf.
  9. Lösung: auch für die innere Schleife eine Referenz verwenden. Ist auch der Vorschlag des Compilers bei help:
  10. Problem: Wörter mit sich selbst vergleichen bringt nichts und Reihenfolge der Paare auch egal, also Paare nur einmal.
  11. Lösung: innere Schleife erst ab dem n+1-ten Element, dafür Position der Elemente
    • geht mit enumerate von Iterator, daher einen Iterator für words erstellen, aber nicht words in einen Iterator umwandeln: words.iter().enumerate() liefert Paar (i,w1), Rust kann Dekomposition
    • für die innere Schleife brauchen wir also nur noch den Abschnitt (Slice) des Vektors: &words[i + 1..]

Fehlerbehandlung

  1. Aufrufe der Abstandsfunktionen in Schleife übertragen: assert\(_eq\)?!((?\(.*\)(".* → println!("\2 distance of {} and {}: {}", w1, w2, \2(w1, w2));

    match hamming(w1, w2) {
        Ok(distance) => println!("Levenshtein distance of {} and {}: {}", w1, w2, distance),
        Err(why) => panic!("{:?}", why)
    }
    
    
    println!("Levenshtein distance of {} and {}: {}", w1, w2, levenshtein(w1, w2));
    
    
    println!("Normalized Levenshtein distance of {} and {}: {}", w1, w2, normalized_levenshtein(w1, w2));
    
    
    println!("OSA distance of {} and {}: {}", w1, w2, osa_distance(w1, w2));
    
    
    println!("Damerau-Levenshtein distance of {} and {}: {}", w1, w2, damerau_levenshtein(w1, w2));
    
    
    println!("Normalized Damerau-Levenshtein distance of {} and {}: {}", w1, w2, normalized_damerau_levenshtein(w1, w2));
    
    
    println!("Jaro distance of {} and {}: {}", w1, w2, jaro(w1, w2));
    
    
    println!("Jaro-Winkler distance of {} and {}: {}", w1, w2, jaro_winkler(w1, w2));
    
    
    println!("Sorensen-Dice distance of {} and {}: {}", w1, w2, sorensen_dice(w1, w2));
    
  2. Im Vektor "Test" hinzufügen führt zu einer panic
  3. Fehlerbehandlung:

    match hamming(w1, w2) {
        Ok(dist) => println!("Hamming distance of {} and {}: {}", w1, w2, dist),
        Err(StrSimError::DifferentLengthArgs)
            => println!("Hamming distance of {} and {} not possible", w1, w2),
    }
    

Wörter von Stdin lesen

  1. praktisch wäre es, wenn man die Wörter zeilenweise über die Standardeingabe übermitteln kann; Suche in der Rust-Stdlib-Dokumentation nach »stdin«; io::stdin klingt gut; Beispiel von dort
  2. die Wörter sollen zeilenweise; für struct Stdin gibt es read_line mit Beispiel

    let stdin = io::stdin();
    let mut stdin = stdin.lock();
     
    let mut words = Vec::new();
    loop {
        let mut input = String::new();
        match stdin.read_line(&mut input) {
            Ok(_) => words.push(input),
            Err(_) => break,
        }
    }
    
  3. Problem: Dateiende (^D, Strg+D) funktioniert nicht. Ok-Zeig untersuchen: Ok(n) => { println!("{}", n); words.push(input); }

  4. Erkenntnis: Dateiende ist kein Fehler (wie bei fread in C), sondern eine leere Eingabe, umbau zu:

    match stdin.read_line(&mut input) {
        Ok(n) if n == 0 => break,
        Ok(_) => words.push(input),
        Err(error) => unimplemented!("error: {}", error),
    }
    
  5. Zeilenumbrüche weg:

    Ok(_) => {
        if input.ends_with('\n') {
            input.pop();
            if input.ends_with('\r') {
                input.pop();
            }
        }
        words.push(input);
    }
    

Worte von der Kommandozeile übernehmen

  1. Praktisch wäre es ja auch, Wort von der Kommandozeile zu lesen; gutes Crate für Kommandozeile ist clap; es gibt eine Neuentwicklung 3.0, die noch beta ist: c add clap@3.0.0-beta
  2. einbinden:

    use clap::{
        crate_authors,
        crate_description,
        crate_name,
        crate_version,
        App,
        Arg,
    };
     
    let args = App::new(crate_name!())
        .version(crate_version!())
        .author(crate_authors!(", "))
        .about(crate_description!())
     
        .arg(Arg::new("words")
              .multiple_values(true)
              .multiple_occurrences(true)
              .value_name("WORD")
        ).get_matches();
    
  3. automatische Hilfe c r -- --help

  4. Rust-Magie:

    let stdin_words;
    let words : Vec<&str>;
    if let Some(v) = args.values_of("words") {
        words = v.collect();
    } else {
        let stdin = io::stdin();
        let mut stdin = stdin.lock();
     
        let mut w = Vec::new();
        …
        stdin_words = w;
        words = stdin_words.iter().map(|w| w.as_str()).collect();
    }
    

Kommandozeilenoptionen – Makros

  1. für jeden Algorithmus soll es eine Kommandozeilenoption geben und --all für alle (Fleißarbeit)

    .arg(Arg::new("hamming")
         .short('h')
         .long("hamming")
         .about("compute Hamming distance")
    ).arg(Arg::new("levenshtein")
          .short('l')
          .long("levenshtein")
          .about("compute Levenshtein distance")
    ).arg(Arg::new("norm_levenshtein")
          .short('L')
          .long("normalized-levenshtein")
          .about("compute normalized Levenshtein distance")
    …
    ).arg(Arg::new("all")
          .short('a')
          .long("all")
          .about("compute all distance metrics")
    ).arg(Arg::new("words")
    
  2. Abfrage der Argumente

    if args.is_present("all") || args.is_present("hamming") {
        match hamming(w1, w2) {
            Ok(dist) => println!("Hamming distance of {} and {}: {}", w1, w2, dist),
            Err(StrSimError::DifferentLengthArgs)
                => println!("Hamming distance of {} and {} not possible", w1, w2),
        }
    }
    
  3. für die anderen: if args.is_present("all") || args.is_present("…") { »Hilfe, die Arbeit!«

  4. Lösung: Makro

    macro_rules! dist {
        ($args:ident, $arg:literal, $name:literal, $func:ident, $w1:ident, $w2:ident) => (
            if $args.is_present("all") || $args.is_present($arg) {
                println!(concat!($name, " distance of {} and {}: {}"), $w1, $w2, $func($w1, $w2));
            }
        );
    }
     
    dist!(args, "levenshtein", "Levenshtein", levenshtein, w1, w2);
    dist!(args, "norm_levenshtein", "Normalized Levenshtein",
          normalized_levenshtein, w1, w2);
    

Release

  1. git add . && git ci -m 'First commit'
  2. Version in Cargo.toml auf 1.0.0 setzen und übersetzen c b
  3. git commit -a -m 'Release 1.0.0'
  4. c install --path=.
  5. geschafft

Ergebnisse

  1. ähnliche Worte ermitteln:

    print -l src/Stichwort/**/*~*/index.md(.:t:r) \
      |word-dist -Djs \
      |LCC sort -n -t: -k2 -r |column -s: -t L
    
  2. Yaml-Datei mit den Ersetzungen alt: neu anlegen

  3. Massenkorrektur im Quelltext:

    for i in ${(f)"$(<bad-tags.yaml)"}
    do
        x=( ${(s,: ,)i} )
        echo -n "Looking for $x[1]..."
        files=( $(TIMEFMT=; g -c core.quotepath=false grep -l "\!tag.* ${x[1]}[] ]") )
        echo "$#files matches"
        (( $#files )) && sed -Ei "/\!tag/s, ${x[1]}([] ]), ${x[2]}\\1," $files
    done