aehnlichkeitsvergleich zweier listen

[marcdevil]

hi
ich habe zwei textfiles,in denen pro zeile ein (buch)titel steht, diese (buch)titel sind etwas schlampig eingetragen, koennen also etwas anders heissen als in der anderen liste.
ich moechte nun diese beiden listen auf aehnlichkeit hin untersuchen lassen und die unikate der jeweiligen listen ausgeben lassen.

liste 1:
faust I
faust II
conan der barbar
es
Alice im Wunderland

liste 2:
Faust
Faust 2
Conan der Barbar - Das Buch zum Film
Hollowman

Am besten waere es, wenn er fuer Liste 1:
es
Alice im Wunderland

und Liste 2:
Hollowman
ausgibt

und bei
Conan nachfragt

also I oder nix = 1 (Faust 1)
caseinsensitiv (faust = Faust)
bei einzelbuchstabenmutation (Faust = Vaust)
und anhaengsel evtl. nachfragen (abschaltbar > immer true)

ich hoffe mein textblastscript wird was!
ciao

[Oliver@Home]

hy,

es gibt ein tool namens "diff"

weiss aber nicht genau ob es das ist was du suchst!? mit diff kannst du zwei dateien vergleichen.

z.b. diff datei1 datei2

gruß
oliver

[Hans-Georg Normann]

Hi mardevil

siehe auch die Befehle comm und cmp. Dokumentation kann über man .... eingesehen werden.

Hans

[marcdevil]

also diff,comm und cmp finden nur 100%ige
übereinstimmungen,
ich untersuche jedoch wie beschrieben
auch abarten, anhängsel und punktmutationen

[thommy]

Prinzipiell ist so etwas mit einem Skript möglich, aber bei dem Aufwand wirst Du wohl niemanden finden, der sich der Sache annimmt.

Mein Lösungsansatz wäre zunächst das "diff" über beide Dateien. Jetzt erhälst Du ALLE Unterschiede, d.h. die Übereinstimmungen sind schon einmal raus.

Und nun beginnt der ganze Aufwand. Du musst Du diff-Ausgabe nach ähnlichen Zeilen scannen. Da die Zeilen immer paarweise aufeinander folgen, ist der Zugriff simple, aber daraus zu entscheiden, ob die Abweichung in der Toleranz liegt... naja, es müssten Funktionen geschrieben werden, die jeden Deiner Fälle prüfen. Groß- und Kleinschreibung ist einfach, das kannst Du in der Bash abschalten. Aber der Rest wird nur über ziemlich komplizierte Suchmuster und "grep" oder "sed" funktionieren.

Eine interessante Sache, so etwas zu "programmieren". Aber ich bräuchte vermutlicht Stunden, sorry :(

Thomas

[marcdevil]

hi thommy
ich dachte es gibt doch schon sowas, evtl. als option von diff.
naja dann muss ich es wohl doch mit sed machen, damit kenn ich mich halbwegs aus.
das mit der funktion ueber die toleranz habe ich nur noch nicht ganz verstanden, wie ich das in einem script realisieren soll.
c, oder so was kann ich nicht, nur sh-script.

[thommy]

Toleranz...

Ich spiele damit auf Deine verschiedenen Kriterien an, nach denen zwei ähnliche Einträge als gleich behandelt werden soll. Du wirst unmöglich alle Kriterien in einem Stück testen können, sondern immer schön der Reihe nach. Ich würde jeden Test in eine eigene Funktion packen und die Funktionen solange ansetzen, bis eine ein "ok" zurück gibt, oder alle scheiterten.

Paar Informationen zur Shellprogrammierung stehen in der Linuxfibel (Bashprogrammierung) (http://www.linuxfibel.de/bashprog.htm).

Thomas

[jgbauman]

Hi,

Mein Vorschlag waere einen Normierungsfilter zu schreiben, jede Datei fuer sich zu normieren und sortieren und dann mit diff drueber zu gehen.

Die Aufgabe ist sicher nicht vollstaendig loesbar, aber mit obiger Methode kommt man vielleicht schnell relativ weit.

moegliche Normierungen:
* alles in Grossbuchstaben umwandeln
* mehrere Lehrzeichen zu einem zusammenfassen
* Satzzeichen entfernen
* Umlaute plaetten (ä->ae)
* roemische Zahlen zu arabischen
* Einses (1) entfernen
* Artikel entfernen
* ...
(eventuell Abhaengigkeiten/notwendige Reihenfolge beachten)

Wie gross sind den die Listen.

[marcdevil]

mit der normierung habe ich als erstes angefangen.
auf die idee mit den leerzeichen und den
artikeln bin ich allerdings nicht gekommen,
haengt aber auch von den listen ab.
diese normierung die fuer jede liste bei mir
nun eine elendlange zeile aus gepipten
sedbefehlen und ist auch nicht sonderlich
schnell: mal sehen, wie lange das mit meiner
1500 zeiligen liste geht. brauche nur noch
eine 2. liste zum vergleichen.

ich denke, das ich die abarten selber checken
sollte, das kann ein programm nicht entscheiden,
wenn eine punktmutation mal richtig
(gleicher titel, anders geschrieben)
und mal falsch ist (aehnlicher titel, verschiedene werke)

trotzdem dank

[jgbauman]

Eine bessere Loesung (aber bei nur 1500 Titeln lohnt der Aufwand wohl kaum und ist als Shellskript wohl auch nicht mehr zu realisieren) waere eine eigene Vergleichsfunktion zu schreiben, die ihre Ergebnisse gewichtet.

Vergleich zweier Titel Stueck fuer Stueck (Stueck wahrscheinlich meist Buchstabe, aber ewentuell auch mehrere Zeichen wie ' ' (viele Lehrzeichen) 'ae' 'II' 'IV', die)

Das Gesamtergebnis ist das Produkt der Einzelergebnisse (grad der uebereinstimmugn [0 (sehr schlecht) bis 1 (vollkommene Uebereinstimmung]

Nicht unbedingt eindeutige Einteilung der Titel in Stuecke z.B.
g|o|e|t|h|e
vs.
g|oe|t|h|e

Einfache Loesung: Erzeuge fuer ein Titelpaar A und B die Mengen AL und BL die alle Lesarten von A bzw. B enthalten.
Während der Bestimmung der Lesarten koennen Normierungschritte vorgenommen werden.
Bestimme fuer alle Kombinationen der Elemente von AL und BL einen Aehnlichkeitsfaktor und waehle den besten.

Bessere Vergleicher koennten auch fehlende oder uberzaehlige Stuecke beruecksichtigen (mit geigneten Faktoren) und auf zwei ebenen Arbeiten (Woerter und Titel) und somit ausgelassene Buchstaben auf Wortebene und ausgelassene Titel auf Satzebene beruecksichtigen.

Nachteil, bei ungeschickter Implementierung vermutlich hohe Laufzeiten.

Kannst mir ja mal zwei Listen schicken,
vielleicht probier ich mal sowas in Python wenn ich grad lustig bin.