Dopasowywanie przybliżonego ciągu znaków w magazynie danych podstawowych

Question

Mam mały problem z główną aplikacją danych, którą aktualnie piszę. Mam dwa różne modele, konteksty i trwałe sklepy. Jedna dotyczy danych mojej aplikacji, druga dotyczy strony z odpowiednimi informacjami.

W większości przypadków dopasowuję dokładnie jeden rekord z mojej aplikacji do innego rekordu z drugiego źródła. Czasami jednak muszę zrezygnować z rozmytego dopasowania ciągów, aby połączyć dwa rekordy. Próbuję dopasować tytuły piosenek. Mój lokalny tytuł mógłby być (złożony) "The French Idealist is in your pensée" a pilot tytuł piosenka mogłaby być "01 - 10 - French idealist in in you're pensee, The (dub remix, feat. DJ Objective-C)"

wyszukiwać przepełnienie stosu, Google, dokumentacja kakao, i nie mogę znaleźć żadnej jasnej odpowiedzi na temat jak zrobić rozmyty dopasowanie w tych przypadkach. Moje ciągi mogą zaczynać się od wszystkiego, mają kilka znaków specjalnych, zwykle kończą się losowymi lub zignorowanymi postaciami.

Regexp nie zrobi, ani NSPredicates, Soundex nie działa dobrze z obcymi nazwami, a może Levenshtein nie wystarczy (lub będzie?).

Szukam tytułu w zestawie kilkunastu potencjalnych meczów, ale muszę wykonać tę operację całkiem sporo. 100% celność nie jest celem.

Zastanawiam się nad usunięciem zignorowanych słów, wyodrębnienie słów kluczowych (w tym przykładzie "francuski, idealista, pensée"), połączenie ich, a następnie użycie odległości Levenshtein (słowa w tytule utworu powinny być w tej samej kolejności).

W moim szczególnym przypadku, czy to działa? Jaki jest standard branżowy w odniesieniu do tego problemu (nie mogę być jedynym na świecie, który chce dopasować nieco inne nazwy piosenek) Czy Core Data, Cocoa lub Objective-C mogą mi pomóc?

Wielkie dzięki.

Answer 1

Chcesz, aby wyszukiwanie było niedopasowane diakrytycznie, aby pasowało do "é" w pensée i "e" w pensee. Otrzymasz to dodając [d] po atrybucie. Podobnie jak w przypadku:

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

'C' w [cd] dotyczy niewrażliwości na wielkość liter.

Ponieważ twój ciąg znaków może pojawić się w dowolnej kolejności w szukanym łańcuchu, możesz tokenizować swój łańcuch wyszukiwania ([... componentsByString: @ ""]), a następnie utworzyć predykat taki jak

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

Taka składnia do łączenia predykatów powyżej może być wyłączonym, wychodząc z pamięci.

Answer 2

Uważam, że narzędzie, którego chcesz użyć, to SearchKit. Mówię to tak, jakbym właśnie wykonał twoją pracę łatwo ... Nie, ale powinien mieć narzędzia, których potrzebujesz, aby odnieść sukces tutaj. LNC nadal oferuje ich SearchKit Podcast za darmo (bardzo ładne).

Każda ścieżka byłaby w tym przypadku dokumentem, a trzeba by wymyślić dobry sposób na ich indeksowanie za pomocą identyfikatora, który można wykorzystać do ich znalezienia. Następnie możesz załadować je za pomocą metadanych i przeszukać je. Być może umieszczenie tytułu "w" dokumencie byłoby pomocne w ułatwieniu korzystania z funkcji wyszukiwania podobieństw (kSKSearchOptionFindSimilar). To może, ale nie musi działać naprawdę dobrze.

Pytanie, które sobie zadałeś, jest dobre, ale nie ma na pewno standardu branżowego, ponieważ każdy, kto rozwiązuje ten problem dobrze (tj. Każda duża wyszukiwarka), zachowuje swoje algorytmy w tajemnicy. To jest trudny problem; nikt nie jest gotów oddać ich odpowiedzi.

Answer 3

Rozważmy q-gramów, które są podciągami o długości q (Gravano et al., 2001).

Można dla dwóch ciągów s1 i s2 określić dla każdego q-gramu s1 odpowiedni q-gram s2 z najmniejszą odległością edycyjną. Następnie dodaj wszystkie te odległości i otrzymasz metrykę, która jest bardzo odporna na permutację słów i dodatkowych znaków.

Ogólnie q należy dostosować do twojej domeny problemowej (eksperyment z q = 3, 4, 5 ...).