2009-03-13 11 views
1

Sagen wir, ich habe mehrere URLs und gebe den Basisnamen von jeder URL zurück, so;Text analysieren und Ähnlichkeiten zurückgeben

http://www.test.com/the.code.r00 

zurückkehren würde

the.code.r00 

und ich habe mehrere Basisnamen ich aus mehreren URLs extrahiert auf

mit denen
the.code.r00 
the.code.r01 
.. 
... 
the.code.r12 

und zusammen zu arbeiten, habe ich die folgenden Basisnamen zu haben von anderen URLs

the.matrix.r00 
the.matrix.r01 
.. 
... 
the.matrix.r14 

Ich würde gerne wissen, ob es ein bekannter Algorithmus ist die

the.code.r 
the.matrix.r 

nach dem Parsen der Basisnamen ich oben aufgeführt zurückzukehren getestet und bewährt hat.

Auch, wenn stattdessen, gibt es einige * nix-Werkzeug, das das gleiche tut, das wäre super.

Hinweis, das Format ist nicht immer wie oben, sonst hätte ich ein einfaches substr. Die Nummern sind nicht immer an einer bestimmten Stelle in der Zeichenfolge aufgeführt. Einige andere Beispiele;

the.code.part01.rar 
the.code.001 
.. 
.... 

Ich konnte meinen eigenen Algorithmus implementieren, dies zu tun, aber es würde wahrscheinlich eine Dose Bugs ohne einige schwere Prüfung sein, damit ich einen bekannten Algorithmus zu verwenden, würde es vorziehen, wenn es eine bereits definiert ist ..

Antwort

3

Sie suchen wahrscheinlich nach einer verankerten Implementierung des longest common substring problem. Sortieren Sie die Liste der Zeichenfolgen und führen Sie das verankerte LCS für die angrenzenden Elemente aus. Fügen Sie die LCS in eine mehrwertige hashmap mit der LCS als Schlüssel und den beiden Strings als Werte ein.

Sobald Sie das haben, machen Sie das Gleiche mit den LCS-Strings, bis Sie einen Schwellenwert erreicht haben.

+0

Gute Antwort, danke für den Link! – Cerebrus

+0

hmm Ich denke, das könnte helfen. Danke –

1

Betrachten Sie jedes Paar Zeichenfolgen in Ihrer Liste und berechnen Sie die Levenshtein Distance (aka Zeichenfolge Bearbeitungsabstand) zwischen ihnen. Dies gibt Ihnen die minimale Anzahl von Änderungen, die notwendig sind, um die eine Zeichenfolge in die andere zu ändern.

Jetzt erhalten Sie von der Levenshtein-Implementierung die tatsächliche Menge der Änderungen zwischen den Strings (durch folgende Backpointer im dynamischen Programm). Wenn dieser Satz von Änderungen nur darin besteht, Zahlen durch andere Zahlen zu ersetzen, haben Sie ein Muster gefunden. Kopieren Sie eine der Zeichenfolgen, entfernen Sie diese Zahlen, speichern Sie sie in Ihrer Mustergruppe, und fahren Sie mit den anderen Zeichenfolgenpaaren fort.

+0

das ist auch hilfreich. Vielen Dank –

Verwandte Themen