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


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

Przez większość czasu 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ł może być (zmyślony) "The French Idealist is in your pensée" i może być tytuł zdalnej piosenki "01 - 10 - French idealist in in you're pensee, The (dub remix, feat. DJ Objective-C)" 

Przeszukuję przepełnienie stosu, Google, dokumentację kakao, i nie mogę znaleźć żadnej jasnej odpowiedzi na temat tego, jak wykonać dopasowanie rozmyte 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 będzie wystarczający (czy też nie?).

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

Zastanawiałem 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.


12
2018-05-19 10:18


pochodzenie




Odpowiedzi:


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. Tak jak w przypadku:

    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"(songTitle like[cd] %@)", yourSongSubstring];
"C" w [cd] oznacza niewrażliwość na wielkość liter.

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

    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"(songTitle like[cd] %@) and (songTitle like[cd] %@)", songToken1, songToken2];
Ta składnia do łączenia powyższych predykatów może być wyłączona, wychodząc z pamięci.


3
2018-05-19 21:00



Po raz pierwszy spróbowałem wariacji tego i kiedy piszę dane z prawdziwego świata, to nie działa. W większości przypadków problemem nie są znaki diakrytyczne czy przypadki, ale różnice w subtelnie pisowni (jak w "Backstreet girl" kontra "Back Street Girl"). To rozwiązanie jest również mocno uzależnione od poprzedniego kroku, tokenizacji, co jest naprawdę trudne dla domeny "słowa, które mogą pojawić się w tytule utworu" - damdamdam


Uważam, że narzędzie, którego chcesz użyć, jest tutaj 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 wciąż oferuje swoje 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.


2
2018-05-19 21:36



SearchKit. Całkowicie zapomniałem o tym API. Spojrzałem bardzo ciężko na dokument, widziałem dla niego natychmiastowe zastosowania w mojej aplikacji, ale myślę, że jest on zbyt zaangażowany tylko po to, aby zaszokować dopasowanie między ciągiem a innym ciągiem. - damdamdam


Rozważać q-gramy, które są podciągami o długości q (Gravano i wsp., 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.

Zasadniczo q powinno być dostosowane do twojej domeny problemowej (eksperyment z q = 3, 4, 5 ...).


1
2018-04-05 11:43