Stellen Sie sich vor, Sie erhalten ein Login auf einem Unixrechner, der auf einer esoterischen Hardware läuft. Auf diesem Rechner finden Sie ein 10-mloc C++/C/Java-Projekt, mit vielen einsatzspezifischen Sprachen und Dateiformaten.
Sie dürfen den Quellcode nicht auf Ihren Rechner kopieren, da dieser dem Kunden gehört. Sie dürfen den Quellcode anpassen und auf dem Rechner kompilieren. Sie dürfen nichts installieren.

Wie soll man sich hier zurechtfinden? Sie können grep versuchen, aber Sie werden an Alterschwäche sterben, bevor Sie alle Stellen gefunden haben, wo das Symbol, für das Sie sich interessieren, vorkommt. Vielleicht haben Sie Glück und GNU-Idutils ist installiert, aber natürlich kommt das Symbol auch in Dateien vor die Idutils nicht kennt und nicht indexiert.

Aber glücklicherweise finden Sie auf dem Rechner Python 2.6 und Sie können die Hilfe eines Ninja in Anspruch nehmen.

Und ja, solche Dinge kommen bei uns vor.

Finja

Finja ist ein Indexer der nur Python 2.6+ (3.4+) benötigt. Anders als viele der grossartigen Alternativen zu Finja, ist Finja generisch. Es weiss nicht, was es indexiert. Finja erreicht gute Qualität durch mehrere Durchgänge in denen der Text auf unterschiedliche Art in Tokens zerlegt wird. Deshalb ist es langsamer und der Index ist grösser als bei spezialisierten Indexern, aber es indexiert Ihren Kram und lässt keine unbekannten Dateien aus.

Finja Benutzen

Ich rufe finja -i im Verzeichnis in dem ich diesen Artikel schreibe auf.

$> finja -i
Makefile: indexed 87/147 (0.592) new: 38 UTF-8
finja-blog.html: indexed 4370/10492 (0.417) new: 1126 UTF-8
finja-blog.rst: indexed 487/1517 (0.321) new: 73 UTF-8
Indexing done

Im Makefile hat es 87 einmalige Tokens gefunden. Tatsächlich hat es in allen Durchläufen 147 Token gefunden, im ersten Durchlauf benutzt es zum Beispiel Leerzeichen als Trennzeichen, in einem zweiten Durchlauf benutzt es Satzzeichen der natürlichen Sprache als Trennzeichen und im dritten Durchlauf benutzt Finja Trennzeichen die in gängigen Programmiersprachen vorkommen. Damit zeigt 0.592 den Zusatzaufwand durch die Durchläufe an (1.0 wäre perfekt, tiefer Kennzahlen sind schlechter). Es hat 38 neue Tokens gefunden und UTF-8 als Kodierung der Datei erkannt. Jawohl, Finja kann die Kodierung erkennen. Um die Effizienz zu steigern, nimmt Finja einfach an, dass die Datei in UTF-8 kodiert ist. Erst wenn es zu einem Dekodierungsfehler kommt, wird die Kodierung detektiert.

Jetzt möchte ich ein paar Ninjas finden.

$> finja ninja
.:
finja-blog.html:    7:<title>Finja - Your friendly finding ninja</title>
finja-blog.html:  696:<div class="document"
finja-blog.html:  697:<h1 class="title">Finja - Your friendly finding ninja</h1>
finja-blog.rst:    1:Finja - Your friendly finding ninja
finja-blog.rst:   16:a ninja.

Die Resultate aus der HTML-Datei interessieren mich nicht.

$> finja -p html ninja
.:
finja-blog.rst:    1:Finja - Your friendly finding ninja
finja-blog.rst:   16:a ninja.

Wir finden also im Order ‘.’ Ninja zwei mal auf Linie 1 und 16. Aber halt, dass ist nicht aktuell.

$> finja -u
finja-blog.rst: indexed 939/2897 (0.324) new: 111 UTF-8

Mit finja -u werden nur Dateien die sich verändert haben neu indexiert.

$> finja -p html ninja
.:
finja-blog.rst:    1:Finja - Your friendly finding ninja
finja-blog.rst:   16:a ninja.
finja-blog.rst:   61:   $> finja ninja
finja-blog.rst:   63:   finja-blog.html:    7:<title>Finja - Your friendly
finja-blog.rst:   65:   id="finja-your-friendly-finding-ninja">
finja-blog.rst:   66:   finja-blog.html:  697:<h1 class="title">Finja - Your
finja-blog.rst:   67:   finja-blog.rst:    1:Finja - Your friendly finding ninja
finja-blog.rst:   68:   finja-blog.rst:   16:a ninja.
finja-blog.rst:   74:   $> finja -p html ninja
finja-blog.rst:   76:   finja-blog.rst:    1:Finja - Your friendly finding ninja
finja-blog.rst:   77:   finja-blog.rst:   16:a ninja.

“Yo dawg, I hear you like searching ninjas, we put ninjas in your search, so you can search ninjas while you search.” Hmm, das Resultat ist etwas Rekursiv, aber wir haben bewiesen, dass der Index aktualisiert wurde.

Wir können auch in Unterverzeichnissen suchen:

$> cd dir/
$> finja -u -p html punctuation
..:
finja-blog.rst:   51:second pass it uses punctuation marks from natural

SQLite kann Ihr Freund sein

Natürlich haben wir mit einem 10 mloc Projekt schnell Leistungsprobleme gefunden. Es stellt sich heraus, dass der Anfrageoptimierer von SQLite dumm ist, dumm ist das richtige Wort, den er ist nicht schlecht, aber nicht so ausgeklügelt wie wir es uns von PostgreSQL gewohnt sind. Standardmässig wird keine Histogrammanalyse gemacht und deshalb werden die Tabellen in einer schlechten Reihenfolge vereinigt. Jedoch wenn man SQLite mit SQLITE_ENABLE_STAT4 kompiliert, was Histogrammanalyse aktiviert, werden die Tabellen immer noch in einer schlechten Reihenfolge vereinigt. Ich mache SQLite keinen Vorwurf, es ist eben nicht PostgreSQL. Wir haben die Anfragen also in Finja optimiert.

SELECT
    COUNT(id) count
FROM
    finja
WHERE
    token_id = ?

Wir überprüfen zu erst wie oft ein Token im Index vorkommt, also sozusagen eine manuelle Histogrammanalyse. Dann vereinigen wir den Index mit dem seltensten Token zuerst.

def search_term_cardinality(term_id):
    db         = get_db(create = False)
    con        = db[0]

    curs = con.cursor()
    res = curs.execute(_token_cardinality, [term_id]).fetchall()
    return res[0][0]

def order_search_terms(search):
    res = sorted(search, key=search_term_cardinality)
    return res

Dies basiert natürlich auf der Annahme, dass die Tokens über mehrere Dateien und Zeilen verteilt sind. Wenn es eine Datei gibt in der sich das Token auf der selben Zeile eine Million mal wiederholt, werden wir eine falsche Entscheidung treffen. Aber in den meisten Fällen ist es viel besser als SQLite entscheiden zu lassen.

Schlusswort

Bitte installieren Sie Finja, nutzen es und falls Sie ein Problem finden eröffnen Sie doch bitte ein Ticket auf Github.

Besten Dank!