Websites bieten ihren Lesern zu einem Thema oft auch noch Links zu Artikeln mit ähnlichen Themen an. Die freie Suchmaschine Elasticsearch findet diese blitzschnell und automatisch, nachdem sie alle Dokumente aus einem Korpus analysiert und indiziert hat.
Wenn Ratsuchende auf Stackoverflow nach Antworten zu Programmierfragen stöbern, steht rechts unten in der Rubrik "Related" immer eine Liste mit Links zu Fragen, die sich mit ähnlichen Themen befassen (Abbildung 1). Das hält die Websurfer bei der Stange, falls mal ein Suchergebnis nicht genau passt oder eine Antwort nicht den gewünschten Gütegrad aufweist. Oft führt dann ein einziger Klick hin zur gesuchten Diskussion. Laut [2] generiert die freie Suchmaschine Elasticsearch ([3]) diese Links auf Stackoverflow in Echtzeit aus der stetig wachsenden und nicht unwesentlichen Sammlung von 10 Millionen Stackoverflow-Beiträgen.
| |
| Abbildung 1: In der Rubrik "Related" rechts unten generiert Stackoverflow mit Elasticsearch Links mit ähnlichen Fragen (bitte einen Pfeil einzeichnen). |
Dabei ist keine richtige Intelligenz am Werk, denn Computer tun sich nach wie vor schwer, den Inhalt eines Dokuments zu verstehen, können also demnach auch keine Dokumente mit verwandten Inhalten finden. Vielmehr stützt sich der verwendete Algorithmus auf einfache Erbsenzählerei, in dem er verschiedene Werte für Worthäufigkeit kombiniert und daraus einen Score ableitet. Elasticsearch hält sich dazu einen sogenannten invertierten Index vor, eine vollständige Liste der unterschiedlichen Wörter, die in allen soweit gespeicherten Dokumenten vorkommen. Jedem dieser eindeutigen Wörter weist der invertierte Index eine Liste mit Dokumenten zu, in denen es vorkommt. So kann Elasticsearch zum Beispiel blitzschnell eine Liste mit Dokumenten zu einem Suchbegriff ausspucken.
 |
| Abbildung 2: Der invertierte Index weist Wörtern Dokumente zu, in denen der Indexer sie fand. |
Sucht ein User zum Beispiel nach dem Begriff "perl", findet Elasticsearch
im invertierten Index aus Abbildung 2 sofort Dokument doc-1 und kann
dieses hoffentlich akkurate Suchergebnis präsentieren.
Bei einer Suche nach zwei Wörtern, wie zum Beispiel
"linux cpan" kommen hingegen zwei Dokumente in Betracht, aber da
doc-2 nur einen Begriff, doc-3 hingegen beide enthält, verpasst
der Algorithmus doc-3 einen höheren Relevanz-Score.
In einer nach dem Score absteigend sortierten Trefferliste steht
Dokument doc-3 dann ganz oben und entspricht wahrscheinlich
eher den Erwartungen des Users.
Aber nicht alle Wörter sind gleich wichtig. Das Wort "file" kommt zum Beispiel
in englischsprachigen Dokumenten zu Computerthemen relativ häufig vor. Sucht
der User nach "file linux cpan", liefern doc-2 und doc-3 jeweils zwei
Treffer, aber da "linux" für ein Dokument signifikanter als "file" ist, bewertet
der Algorithmus "linux cpan" höher als "cpan file" und gibt doc-3 den Vorzug.
Wie wichtig ein Wort in einem Dokument ist, bestimmt das Tf-idf-Maß ([5]). Es weist denjenigen Wörtern einen hohen Wert zu, die einerseits bestimmend im Dokument vorherrschen, aber auch andererseits nicht allzu häufig in weiteren um einen hohen Score buhlenden Dokumenten stehen, also die Einzigartigkeit des Dokuments untermauern. Der Relevanzwert eines Wortes erhöht sich, je häufiger das Wort im Dokument vorkommt (TF=Term Frequency), geht aber zurück, falls das Wort auch in vielen anderen Dokumenten der Sammlung vorkommt (IDF=Inverse Document Frequency).
Um nun die zu einem Dokument X ähnlichen Dokumente in der Datenbank
zu finden, extrahiert Elasticsearch aus X zunächst einmal alle relevanten
Wörter, formt dann daraus eine Suchabfrage, und gibt schließlich
deren Treffer aus ([4]).
Elasticsearch erledigt diese Suche nach ähnlichen Dokumenten ohne viel
Programmieraufwand über das Query-Kommando more_like_this. Allerdings müssen vorher
alle in Frage kommenden Dokumente in den Index wandern, und dafür bietet sich
die Client-Schnittstelle Search::Elasticsearch, der offizielle Perl-Client
für Elasticsearch vom CPAN, an.
Listing 1 kämmt sich durch ein Verzeichnis, in denen eine Reihe von Textdateien
liegen. Es handelt sich um Geschichten aus meinem Blog usarundbrief.com, die
ich mittels eines weiteren Perl-Skripts einfach aus dem handgeschriebenen
Content-Management-System extrahiert habe. Jede Textdatei entspricht also einem
Blog-Eintrag, und in fast 20 Jahren haben sich exakt 877 Einträge angesammelt,
weshalb das Verzeichnis 877 Dateien enthält:
$ ls idx | wc -l
877
$ mlt-index
Added ab-in-die-redwoods.txt
Added abenteuer-verkaufssteuer.txt
Added abrissarbeiten-am-highway-101.txt
Der anschließende Aufruf von mlt-index in Listing 1 schnappt sich die Dateien
der Reihe nach und speist sie mit der Methode index() in den auf meinem
Desktoprechner installierten Elasticsearch-Server (siehe Kasten "Installation") ein.
Wer sein Dateisystem lieber unberührt lässt, fährt mit "vagrant up" und der
Vagrant-Datei in Listing 2 einfach eine VM hoch, installiert dort den Server und
das Mapping "forwarded_port" sorgt dann dafür, dass der in der VM auf Port 9200
lauschende Elasticsearch-Server auch auf dem Haupthost auf Port 9200
ansprechbar ist.
1 VAGRANTFILE_API_VERSION = "2"
2
3 Vagrant::configure(VAGRANTFILE_API_VERSION) do |config|
4
5 # 32-bit Ubuntu Box
6 config.vm.box = "ubuntu/trusty64"
7 config.vm.network "forwarded_port", guest: 9200, host: 9200
8 end
sudo add-apt-repository ppa:webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java7-installer
java -version
wget https://download.elastic.co/elasticsearch/elasticsearch/elasticsearch-1.7.1.deb
sudo dpkg -i *.deb
sudo /etc/init.d/elasticsearch start
Den neu angelegten Index im Server habe ich "blog" genannt, und Zeile 15 in Listing
2 und löscht ihn erst mal, falls er sich schon dort befindet, typischerweise
von einem früheren Aufruf von mlt-index herrührend.
Die find()-Funktion ab Zeile 17 aus dem Perl beiliegenden Modul File::Find
arbeitet sich rekursiv durch alle Dateien unterhalb des angegebenen Verzeichnisses,
wechselt im nutzerdefinierten Callback hinter den Kulissen mit chdir dorthin und
setzt den Namen der aktuell bearbeiteten Datei in der Variablen $_.
Die Methode index() in Zeile 23 fügt mit content den mit slurp() aus
dem Fundus des CPAN-Moduls Sysadm::Install geschlürften Textinhalt der Datei sowie
den Dateinamen unter file in den Index der Suchmaschine ein.
Da die Dateinamen gemäß dem Inhalt des jeweiligen Blogeintrags gewählt sind
(zum Beispiel "ab-in-die-redwoods.txt") braucht die Suchfunktion später bei
Treffern nur den Dateinamen auszugeben.
Die Fütterfunktion index() legt
auch gleich einen neuen Index an, falls dieser noch nicht existert und definiert
außer seinem Namen ("blog") auch noch einen type mit dem Wert text, was im
Elasticsearch-Jargon nichts anderes ist als eine beliebig benamste
Unterabteilung im Index.
01 #!/usr/local/bin/perl -w
02 use strict;
03 use Search::Elasticsearch;
04 use File::Find;
05 use Sysadm::Install qw( slurp );
06 use Cwd;
07 use File::Basename;
08
09 my $idx = "blog";
10 my $base_dir = getcwd;
11 my $base = $base_dir . "/idx";
12
13 my $es = Search::Elasticsearch->new( );
14 eval {
15 $es->indices->delete( index => $idx ) };
16
17 find sub {
18 my $file = $_;
19
20 return if ! -f $file;
21 my $content = slurp $file, { utf8 => 1 };
22
23 $es->index(
24 index => $idx,
25 type => 'text',
26 body => {
27 content => $content,
28 file => $file,
29 }
30 );
31 print "Added $file\n";
32 }, $base;
Das Einspeisen der Daten in Elasticsearch dauerte auf meinem Linux-Desktop
pro ca. 2kB großer Textdatei
etwa eine Zehntelsekunde, sodass dies bei 877 Blogeinträgen schon ordentlich an
meiner Geduld zehrte. Interessanterweise war das Einspeisen auf
meinem Laptop mit SSD und ordentlich RAM
um ein vielfaches schneller, da war in 10 Sekunden alles erledigt.
Ist der Index fertig, können die Abfragen starten. Die Ausgabe
des Kommandos mlt-search in Abbildung 2 zeigt, dass Listing 2 zu einem
Beitrag über das amerikanische Krankenkassensystem als passende Artikel wenig
überraschend als ersten Treffer den gleichen Artikel wiederfindet, aber auch
einigermaßen erstaunliche Ergebnisse, wie zum über den Besuch eines
Schießstandes in South San Francisco. Die Ergebnisse kommen in einem
Sekundenbruchteil zum Vorschein, sodass die Funktion also durchaus auch auf
einer gut besuchten Website ihren Platz hat.
 |
| Abbildung 3: Zu einem Blogeintrag über das amerikanische Krankenkassensystem findet Elasticsearch passende Artikel. |
01 #!/usr/local/bin/perl -w
02 use strict;
03 use Search::Elasticsearch;
04 use Sysadm::Install qw( slurp ) ;
05
06 my $idx = "blog";
07
08 my( $doc ) = @ARGV;
09 die "usage: $0 doc" if !defined $doc;
10
11 my $es = Search::Elasticsearch->new( );
12
13 my $results = $es->search(
14 index => $idx,
15 body => {
16 query => {
17 more_like_this => {
18 like_text =>
19 slurp( $doc, { utf8 => 1 } ),
20 min_term_freq => 5,
21 max_query_terms => 20,
22 }
23 }
24 }
25 );
26
27 for my $result (
28 @{ $results->{ hits }->{ hits } } ) {
29
30 print $result->{ _source }->{ file },
31 "\n";
32 }
Listing 2 nimmt hierzu auf der Kommandozeile den Pfad einer Textdatei
in Empfang, liest diese mit slurp unter Beibehaltung der utf8-Kodierung
ein. Sie schickt deren Inhalt ab Zeile 13 mittels der Methode search() in
einem Query an den Elasticsearch-Server und klaubt aus dem als JSON
zurückkommenden Ergebnis die Namen der Dateien aus den Treffern
mit vergleichbaren Inhalten.
Bei der Funktion more_like_this
gibt der Parameter min_term_freq eine Schwelle für die Selektion eines
Wortes im Referenzdokument an. Steht min_term_freq auf dem Defaultwert
2, muss ein Wort dort mindestens zweimal vorkommen, damit es es in die
Liste der Wörter schaffen kann, mit denen später andere
Dokumente verglichen werden.
Der zweite Parameter max_query_terms ist die Maximalzahl der Wörter
aus dem Originaldokument, die der Algorithmus auswählt, um sie später zu
einem Query zusammenzufassen.
Wer sich weiter über alle denkbaren Methoden der Feinjustierung einer Suchmaschine informieren möchte, dem sei das Anfang des Jahres erschienene O'Reilly-Buch ([2]) empfohlen, das anhand von praktischen Beispielen die Handhabung von Elasticsearch erklärt, Tipps zum Skalieren in großen Clustern gibt und auch einen Blick hinter die Kulissen wirft, wo der Suchengine Apache Lucene sein Wesen treibt.
Listings zu diesem Artikel: ftp://www.linux-magazin.de/pub/listings/magazin/2015/10/Perl
"Elasticsearch: The Definitive Guide", Clinton Gormley und Zachary Tong, O'Reilly, 2015
"Elastische Treffer", Michael Schilli, Linux-Magazin 04/2014, http://www.linux-magazin.de/Ausgaben/2014/04/Perl-Snapshot
"More Like This Query", https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-mlt-query.html
"Tf-idf-Maß" https://de.wikipedia.org/wiki/Tf-idf-Ma%C3%9F
 |
Michael Schilliarbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen der Skriptsprache Perl. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen. |