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

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, документацию по какао, и не могу найти четкого ответа о том, как сделать нечеткое совпадение в этих случаях. Мои строки могут начинаться с чего угодно, иметь набор специальных символов, обычно заканчиваться случайными или игнорируемыми символами.

Регулярное выражение не сработает, как и 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 бесплатно (очень приятно).

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

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

Answer 3

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

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

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