[Trennmuster] Endungen finden

[Stephan Hennig]

Am 15.05.2015 um 21:43 schrieb Tobias Wendorff:

> ich habe mir ein Script gebastelt, welches den längsten gemeinsamen Teil
> eines Strings anzeigt. Ich drehe die Texte zunächst um und vergleiche
> dann jeden String mit jedem über einen LCS-Algorithmus.
> 
> 1. hauptstraße
> 2. dönerstraße
> 3. münsterstraße
> 4. lehrerstraße
> 
> 0. eßartstpuah
> 1. eßartsrenöd
> 2. eßartsretsnüm
> 3. eßartsrerhel
> 
> Das ergibt dann: eßartsre => restraße
> 
> Anschließend ermittle ich die Häufigkeiten der Ergebnisse und bewerte
> die Eigenständigkeit. "restraße" und "straße" kommen natürlich dabei
> raus, erstes muss aber weggefiltert werden.
> 
> Hat jemand eine Idee, wie ich das ein wenig effizienter gestalten könnte?

Was mir in den Sinn kommt: Man kann alle Zeichenketten umgekehrt in
einen Präfixbaum (Trie) einfügen und dabei für jede Kante des Tries
(entspricht einem bestimmten Präfix) einen Zähler mitführen, der bei
Verwendung dieser Kante erhöht wird.  Der Zähler kann im Zielknoten der
Kante gespeichert werden.  Beim Einfügen wird jedes Zeichen eines Wortes
genau einmal angefasst.

Nach dem Einfügen aller Wörter kann man anhand der Zähler unmittelbar
ablesen, wieviele (umgekehrte) Wörter mit dem jeweiligen Präfix
existieren.  Man kann also verschiedenen Präfixe gleichzeitig auszählen.

Viele Grüße,
Stephan Hennig