Die Suche nach der Fuzzy-Search

Unscharfes Suchen ist äußerst hilfreich. Wer länger mit Sublime oder vergleichbaren Editoren gearbeitet hat weiß es zu schätzen, dass er statt eines Datei-Dialogs Strg+p, „filibpost“ und Enter drückt, um etwa files/sql/libs/postgresql-lib.rb zu öffnen. Ich arbeite gerade an einem ähnlichen Hilfskommando, welches das Öffnen in Vim etwa mittels ff filibpost vim ermöglicht. Alles nicht so schwierig – bis auf die sogenannte „Fuzzy Search“.

Zunächst mein (nicht wirklich optimales) Testszenario:

$ tree
.
└── files
    └── sql
        └── libs
            ├── db2-lib.rb
            ├── mariadb-lib.rb
            ├── mysql-lib.rb
            └── postgresql-lib.rb

find + grep

Mit find . -type f werden alle Dateien des aktuellen Verzeichnisses und aller Unterverzeichnisse aufgelistet. Diese werden dann auf den Suchstring überprüft. Da Grep nicht „unscharf“ ist, wird der Suchstring „abc“ mittels $(echo "$1" | sed 's/./&.*/g') in „*a*b*c*“ umgewandelt.

function grep_search {
  fuzzy_search_string=$(echo "$1" | sed 's/./&.*/g')
  find . -type f | grep -i "$fuzzy_search_string"
}

Schwachstellen

Diese Lösung funktioniert und ist auch schnell genug, allerdings sind die Ergebnisse nicht gewichtet. Wenn ich nach „bilderfamilie“ suche, treffen auch sehr tiefe Hierarchien schnell zu. Und wenn sich mein gewünschtes Ergebnis zwischen hunderten Dateien wie ./Bilder/Icons/Faenza/c/22/media-optical-audio-new.png steckt, wird das Herauspicken aufwendig.

find + agrep -p

Dann habe ich über Agrep gelesen, was zunächst vielversprechend klang. Das Tool ist mächtig, aber auch entsprechend etwas komplizierter. Die Option -p war in den Man-Pages jedoch vielversprechend dokumentiert:

agrep -p DCS foo will match „Department of Computer Science.“

function agrep_search {
  find . -type f | agrep -pi $1
}

Schwachstellen

Um es kurz zu machen: Das Ergebnis ist das selbe wie bei dem selbst zusammengesetztem Grep.

find + agrep -By

Okay, Ziel verfehlt. Die „besten“ Treffer sind immer noch nicht oben. Aber dann:

Best match mode. When -B is specified and no exact matches are found, agrep will continue to search until the closest matches (i.e., the ones with minimum number of errors) are found…

Genau was ich will. Wird kein exakter Treffer gefunden, sucht man einen mit einem, dann mit zwei, dann mit drei Fehlern. Klingt gut.

Die Option -B kann nicht vom Stdin lesen (sie muss ja mehrfach durchgehen), daher die etwas andere Implementierung:

function agrep_by_search {
  find . -type f > $HOME/.agrepresults
  agrep -By -S8 -D8 -i $1 $HOME/.agrepresults
  rm $HOME/.agrepresults
}

Schwachstellen

Diese Methode findet nur die besten Lösungen, also die, die mit den wenigsten Fehlern passen. Passt die gesuchte Datei mit drei Fehlern, eine andere aber schon mit zwei, wird die gesuchte nicht angezeigt. Dies ließe sich beheben, in dem man die Funde aus der Zwischenspeicherdatei löscht und die Suche erneut startet, bis die Ergebnisliste mindestens x Einträge hat.

Ein größeres Problem ist aber, dass diese Suchmethode alle Fehlerarten zu berücksichtigen scheint: Einfügung, Ersetzung und Löschung. In einer unscharfen Suche sollten jedoch nur Einfügungen erlaubt sein. Das Heraufsetzen der Kosten von Deletion und Substitution mittels -S8 -D8 scheint leider keinen Unterschied zu machen. So zeigt die Suche nach „mlib“ im obigen Dateisystembeispiel auch Pfade an, die kein m enthalten (siehe folgende Tabelle).

Beispiel-Suchanfragen

./files/sql/libs/mysql-lib.rb
./files/sql/libs/mariadb-lib.rb
./files/sql/libs/postgresql-lib.rb
./files/sql/libs/db2-lib.rb

./files/sql/libs/mysql-lib.rb
./files/sql/libs/mariadb-lib.rb
./files/sql/libs/postgresql-lib.rb
./files/sql/libs/db2-lib.rb

./files/sql/libs/mysql-lib.rb
./files/sql/libs/mariadb-lib.rb
./files/sql/libs/postgresql-lib.rb
./files/sql/libs/db2-lib.rb

./files/sql/libs/mysql-lib.rb
./files/sql/libs/mariadb-lib.rb

./files/sql/libs/mysql-lib.rb
./files/sql/libs/mariadb-lib.rb

./files/sql/libs/mysql-lib.rb
./files/sql/libs/mariadb-lib.rb
./files/sql/libs/postgresql-lib.rb
./files/sql/libs/db2-lib.rb

./files/sql/libs/mysql-lib.rb
./files/sql/libs/mariadb-lib.rb
./files/sql/libs/postgresql-lib.rb
./files/sql/libs/db2-lib.rb

./files/sql/libs/mysql-lib.rb
./files/sql/libs/mariadb-lib.rb
./files/sql/libs/postgresql-lib.rb
./files/sql/libs/db2-lib.rb

./files/sql/libs/mysql-lib.rb
./files/sql/libs/postgresql-lib.rb

Die Suche geht also weiter…