Сопоставление приблизительной строки в хранилище основных данных

Question

У меня небольшая проблема с основным приложением данных, которое я сейчас пишу. У меня есть две разные модели, контексты и постоянные магазины. Один для данных моего приложения, другой для веб-сайта с соответствующей информацией для меня.

В большинстве случаев я сопоставляю ровно одну запись из моего приложения с другой записью из другого источника. Однако иногда мне приходится прибегать к нечеткому сопоставлению строк, чтобы связать две записи. Я пытаюсь сопоставить названия песен. Мое местное название может быть (составлено) "The French Idealist is in your pensée", а название удаленной песни может быть "01 - 10 - French idealist in in you're pensee, The (dub remix, feat. DJ Objective-C)"

Я ищу переполнение стека, Google, документацию по какао, и не могу найти четкого ответа о том, как сделать нечеткое совпадение в этих случаях. Мои строки могут начинаться с чего угодно, иметь набор специальных символов, обычно заканчиваться случайными или игнорируемыми символами.

Regexp не подойдет, как и NSP Предикаты, Soundex плохо работает с иностранными именами, и, возможно, Левенштейна будет недостаточно (или это будет?).

Я ищу заголовок в наборе из примерно дюжины возможных совпадений, но я очень хочу проделать эту операцию. 100% точность не является целью.

Я думал об удалении пропущенных слов, извлечении ключевых слов (в этом примере «французский, идеалист, пенсе»), их объединении и затем использовании расстояния Левенштейна (слова в названии песни должны быть в том же порядке) ,

В моем особом случае это сработало бы? Каков отраслевой стандарт в отношении этой проблемы (я не могу быть единственным в мире, кто хочет сопоставлять слегка разные названия песен) Могут ли Core Data, Cocoa или Objective-C помочь мне?

Большое спасибо.

Answer 1

Вы хотите, чтобы ваш поиск был нечувствительным к диакритическим знакам, чтобы соответствовать 'é' в pensée и 'e' в pensee. Вы получите это, добавив [d] после атрибута. Вот так:

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

'c' в [cd] означает нечувствительность к регистру.

Поскольку ваша строка может появляться в любом порядке в строке, которую вы ищете, вы можете маркировать строку поиска ([... componentsByString: @ ""]), а затем создать предикат, подобный

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

Этот синтаксис для объединения предикатов выше может быть выключен, уходя из памяти.

Answer 2

Я считаю, что вы хотите использовать инструмент SearchKit . Я говорю это так, как будто я только что облегчил вашу работу ... У меня нет, но в ней должны быть инструменты, необходимые для успеха здесь. LNC все еще предлагает их SearchKit Podcast бесплатно (очень приятно).

В этом случае каждый трек был бы документом, и вам нужно было бы найти хороший способ проиндексировать их с помощью идентификатора, который можно использовать для их поиска. Затем вы можете загрузить их с метаданными и искать их. Возможно, здесь будет полезно добавить заголовок «в» документе, чтобы упростить использование поиска сходства (kSKSearchOptionFindSimilar). Это может или не может работать очень хорошо.

Вопрос, который вы задали, является хорошим, но для него, безусловно, нет отраслевого стандарта, потому что любой, кто хорошо решает эту проблему (т. Е. Каждый крупный поисковик), держит свои алгоритмы в секрете. Это сложная проблема; никто не готов отдать свой ответ.

Answer 3

Рассмотрим q-грамм , которые являются подстроками длины q ( Gravano et al., 2001 ).

Для двух строк s1 и s2 вы можете определить для каждой q-граммы s1 соответствующую q-грамм s2 с наименьшим расстоянием редактирования. Затем добавьте все эти расстояния, и вы получите метрику, которая очень устойчива к перестановке слов и дополнительных символов.

Как правило, q следует адаптировать к вашей проблемной области (поэкспериментируйте с q = 3, 4, 5 ...).