Übereinstimmen einer ungefähren Zeichenfolge in einem Core Data Store

Question

Ich habe ein kleines Problem mit der Kerndatenanwendung, die ich gerade schreibe. Ich habe zwei verschiedene Modelle, Kontexte und permanente Speicher. Einer ist für meine App-Daten, der andere ist für eine Website mit relevanten Infos zu mir.

Die meiste Zeit, ich genau einen Datensatz von meiner App zu einem anderen Datensatz aus der anderen Quelle übereinstimmen. Manchmal muss ich jedoch auf einen unscharfen String-Abgleich zurückgreifen, um die beiden Datensätze zu verknüpfen. Ich versuche Titel zu finden. Mein lokaler Titel könnte die (aus) sein "The French Idealist is in your pensée" und der Remote-Songtitel "01 - 10 - French idealist in in you're pensee, The (dub remix, feat. DJ Objective-C)"

Ich suche Stack-Überlauf sein könnte, Google, die Kakao-Dokumentation, und ich keine klare Antwort, wie man ein Fuzzy Matching zu tun finden in diesen Fällen. Meine Strings können mit allem beginnen, haben eine Reihe von Sonderzeichen, enden normalerweise mit zufälligen oder ignorierten Zeichen.

Regexp wird nicht tun, noch NSPredicates, Soundex funktioniert nicht gut mit fremden Namen, und vielleicht wird der Levenshtein nicht genug sein (oder wird es?).

Ich bin auf der Suche nach einem Titel in einem Satz von etwa einem Dutzend möglicher Übereinstimmungen, aber ich muss diese Operation ziemlich viel tun. 100% Genauigkeit ist nicht das Ziel.

Ich dachte daran, die ignorierten Wörter zu entfernen, die Schlüsselwörter (in diesem Beispiel "französisch, idealistisch, pensée") zu extrahieren, sie zu verketten und dann die Levenshtein-Distanz zu verwenden (Wörter in Songtitel sollten in der gleichen Reihenfolge sein)).

In meinem speziellen Fall würde es funktionieren? Was ist der Industriestandard in Bezug auf dieses Problem (ich kann nicht der Einzige auf der Welt sein, der etwas andere Songnamen abgleichen möchte) Können Core Data, Cocoa oder Objective-C mir helfen?

Vielen Dank.

Answer 1

Sie möchten, dass Ihre Suche diakritisch unempfindlich ist, damit sie mit den Buchstaben "é" in pensée und "e" in pensee übereinstimmt. Sie erhalten dies, indem Sie nach dem Attribut [d] hinzufügen. So ähnlich:

NSPredicate *predicate = [NSPredicate predicateWithFormat:@"(songTitle like[cd] %@)", yourSongSubstring];

Das 'c' in [cd] ist für Groß- und Kleinschreibung.

Da Ihre Zeichenfolge in der von Ihnen gesuchten Zeichenfolge in beliebiger Reihenfolge auftreten kann, könnten Sie Ihre Suchzeichenfolge ([... componentsByString: @ ""]]) dann ein Prädikat wie

NSPredicate *predicate = [NSPredicate predicateWithFormat:@"(songTitle like[cd] %@) and (songTitle like[cd] %@)", songToken1, songToken2];

erstellen, um Prädikate oben zu kombinieren geh aus, geh aus dem Gedächtnis.

Answer 2

Ich glaube, das Werkzeug, das Sie hier verwenden möchten, ist SearchKit. Ich sage das, als ob ich deine Arbeit einfach gemacht hätte .... Ich habe es nicht, aber es sollte die Werkzeuge haben, die du brauchst, um hier erfolgreich zu sein. LNC bietet immer noch ihre SearchKit Podcast kostenlos (sehr nett).

Jede Spur wäre in diesem Fall ein Dokument, und Sie müssten eine gute Möglichkeit finden, sie mit einer Kennung zu indizieren, mit der sie gefunden werden können. Sie können sie dann mit Metadaten laden und durchsuchen. Vielleicht wäre es hilfreich, den Titel "in" das Dokument zu setzen, um die Verwendung von Ähnlichkeitssuche (kSKSearchOptionFindSimilar) zu erleichtern. Das kann oder kann nicht wirklich gut funktionieren.

Die Frage, die Sie gestellt haben, ist eine gute, aber es gibt sicherlich keinen Industriestandard dafür, weil jeder, der dieses Problem gut löst (d. H. Jede große Suchmaschine), ihre Algorithmen sehr geheim hält. Dies ist ein schweres Problem; niemand ist bereit, ihre Antwort zu geben.

Answer 3

Betrachten Sie q-Gramm, die Teilzeichenfolgen der Länge q (Gravano et al., 2001) sind.

Sie könnten für zwei Strings s1 und s2 für jedes q-Gramm von s1 das entsprechende q-Gramm von s2 mit der kleinsten Bearbeitungsdistanz bestimmen. Fügen Sie dann alle diese Entfernungen hinzu und Sie erhalten eine Metrik, die sehr robust gegenüber der Permutation von Wörtern und zusätzlichen Zeichen ist.

Generell sollte q an Ihre Problemdomäne angepasst werden (Experiment mit q = 3, 4, 5 ...).