{String » Python} Algorithmus zum Erstellen von einem Prozentsatz von Gemeinsamkeiten zwischen zwei Listen @CODEKICKER

Algorithmus zum Erstellen von einem Prozentsatz von Gemeinsamkeiten zwischen zwei Listen

                    ich möchte den prozentsatz der gemeinsamkeiten zwischen zwei listen herausfinden. sprich wie ähnlich sind sich die strings innerhalb der zwei listen

gibt es dazu bereits existierende algorithmen?

ich habe mich bereits mit den folgenden techniken beschäftigt:

- google's diff-match-patch
- python's diff
- nltk
- levenshtein distance

07.03.2011

burner007

790 ● 1 ● 9

		für eine genauere aussage müsste man nochmal definieren, was genau mit dem Prozentsatz ausgedrückt werden soll (siehe unten) – CRegenschein 07.03.2011
		Nur eine Rückfrage: Bist Du bei dem Problem weiter gekommen? – CRegenschein 09.03.2011
		habe das problem gelöst! post gibs bald – burner007 16.03.2011

3 Antworten

                    Es gibt auch noch 

* Hamming Distanz
* Euklidischer Abstand
* Pearson Korrelation

u. v. a. m.

Was genau meinst Du denn mit, gibt es dazu bereits existierende Algorithmen?
Existierende Algorithmen für die "Ähnlichkeit" (oder den "Abstand") von zwei Strings hast Du ja in diesem Thread schon zu Hauf (Levenshtein, Hamming, Euklid, Pearson, ...) ;-)

Grüße
CRegenschein
                    
                

07.03.2011

CRegenschein

635 ● 1 ● 9

		genau, zwei strings vergleiche ich bereits aber zwei listen von strins noch nicht man kann natürlich die anzahl der sehr ähnlichen strings zählen und in ein verhältnis zur anzahl der keywords stellen. somit bekommt man schon einen prozentsatz ich möchte nur gerne wissen ob es schon einen algorithmus gibt, oder wie man diese recht einfach selbst erstellen kann, der genau 2 listen von keywords vergleicht und einen prozentsatz der gemeinsamkeiten zurück gibt – burner007 07.03.2011
		Recht "einfach" wäre ja, den Prozentsatz an Strings zu ermitteln, die in beiden Strings identisch vorkommen. Hierbei ist es sicher sinnvoll, die Listen vorher lexikalisch zu sortieren. Außerdem wäre auch eine Art threshold sinnvoll. Zum Beispiel sind die Wörter and und sand band wand land usw. recht 'ähnlich'... aber wie will man nun hier in dieser kleinen Liste einen "Prozentsatz" an Ähnlichkeit ermitteln? – CRegenschein 07.03.2011
		aeh... die in beiden Listen identisch vorkommen sogar ;) – CRegenschein 07.03.2011

so sollte es Funktionieren:

List<string> list1 = new List<string>();
list1.AddRange(new[] { "and", "sand", "band", "wand" });

List<string> list2 = new List<string>();
list2.AddRange(new[] { "und", "bund", "band", "wand" });

var matches = list1.Join(list2,
      (l1 => l1.ToString()),
      (l2 => l2.ToString()),
      ((l1, l2) => new { list1 = l1, list2 = l2 }));
      

var prozent = ( 200 / ( list1.Count + list2.Count ) ) * matches.Count();
      
Console.WriteLine(prozent + "%");     
Console.ReadKey();

//Ergebnis:
// = 50%
// 2 der 4 Wörter in jeder Liste stimmen überein. Reihenfolge der Wörter ist egal

07.03.2011

Floyd

11,0k ● 3 ● 9

		Ja, damit werden die identischen Strings abgefackelt... aber es geht ja auch noch um eine "Ähnlichkeit" zwischen zwei Strings... wenn ich die Frage richtig verstanden habe. Also, wieviel Prozent der Wörter in der Liste sind einander ähnlich? Wenn man nun eine Levenshtein Distanz von 2 als Treshold nehmen würde, wären 100% der Wörter oben einander ähnlich... – CRegenschein 07.03.2011
		Dann muss man den Linq-Ausdruck entsprechend anpassen. Für Levenshtein gibt es zum Beispiel effizente .Net-Implementierungen. Müßte sich der Thread-Owner bitte einmal äußeren damit ich ggf. das Beispiel anpassen kann. Die grundsätzliche Implementierung bleibt aber die selbe (incl. Prozentberechnung). – Floyd 07.03.2011
		@ floyd bitte gib wenn möglich nur python code an und auch wie CRegenschein schon angedeutet hat, soll auch überprüft werden wie ähnlich sich zwei strings sind. grundsätzlich habe ich bereits eine funktion die identische wörter findet und zählt – burner007 08.03.2011
		Ach misst. Das es um Python geht aber ich komplett überlesen -.- – Floyd 08.03.2011

Vielleicht hilft:

Frage bei SO

bei der Klärung von weiteren Aspekten der Spezifikation und mit etwas Glück passt sogar "Tanimoto coded as a Python function".

07.03.2011