Какой самый лучший способ разобрать лексикон и показать большое количество совпадений с использованием подстановочных знаков - PullRequest
Новая
       30

Какой самый лучший способ разобрать лексикон и показать большое количество совпадений с использованием подстановочных знаков

4 голосов
/ 13 июня 2011

Моя проблема в том, что у меня есть словарь около 200 000 слов или около того.Размер файла составляет 1,8 МБ.Мне нужен ввод от пользователя, скажем ** id, и я хочу показать все возможные совпадения, где * может быть любая буква AZ.(говорит, горничная и т. д.)

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

Моя идея состояла в том, чтобы попытаться использовать RegexKitLite, но у меня есть ощущение, что это будет невероятно медленно.

Спасибо за любой вклад!

Редактировать: Как вы думаете,можно ли использовать NSPredicates для достижения этой цели?

1 Ответ

4 голосов
/ 13 июня 2011

То, что вы можете сделать для оптимизации производительности поиска, во многом зависит от того, как вы хотите ограничить использование этих подстановочных знаков.

Точно: каковы характеристики ваших групповых символов?

  • только для префиксов подстановочные знаки (m /. + Foobar /)
  • только суффикс подстановочные знаки (m / foobar. + /)
  • атомные подстановочные знаки (m/./)
  • динамические подстановочные знаки (m/.+/)

Подстановочные знаки только для префиксов

Используйте Префиксное дерево или DAWG

Подстановочные знаки только для суффикса

Используйте Дерево суффиксов или DAWG

Атомные символы

Один из способов радикально сократить количество матчей, которые вы должны провести:

Создание BKTree из вашей коллекции слов .

Поскольку (и до тех пор, пока) ваш подстановочный знак имеет фиксированную длину (1 в вашем случае), вы можете просто запросить у вашего BKTree узлы с точным расстоянием редактирования n, при этом n будет количеством подстановочных знаков , Традиционные запросы BKTree имеют верхний предел отклонения . В вашем случае вы бы хотели ввести дополнительный нижний предел , сузив диапазон допустимого отклонения до ровно [n,1] (по сравнению с традиционно [0,n]). Вы получите массив слов, отличающийся от вашего слова запроса точными n символами.

Для запроса **id возможны следующие совпадения:

  • void (2 добавления)
  • laid (2х дополнений)
  • bad (1 замена, 1 добавление)
  • to (2 замены)

Хотя это еще не правильные совпадения для вашего запроса , они представляют собой очень маленькое подмножество всего набора слов.

И последнее, но не менее важное: вы запускаете повторное сопоставление Regex, получая эти результаты и возвращают все оставшиеся совпадения .

BKTrees вводят расстояние Левенштейна как некоторую пространственную эвристику , чтобы резко ( в зависимости от энтропии в вашей коллекции слов) уменьшить количество требуемых сравнение / паросочетания .

Для получения дополнительной оптимизации вы можете использовать несколько BKTrees :

Разделите вашу коллекцию на подмножества. Один набор для слов длиной 1, один для длины 2, один для 3 и так далее. Из каждого подмножества вы затем строите BKTree. Для запроса **id вы должны запросить BKTree для длины 4 (подстановочные знаки считаются как символы).
Это относится к подстановочным знакам, которые интерпретируются как m/./. Однако если ваш подстановочный знак будет интерпретирован как m/.?/, вы запросите BKTrees для длины 3 и 4.

В качестве альтернативы - BKTrees вы также можете использовать GADDAG , который представляет собой структуру данных (специализация Trie), специально предназначенную для Поиски в стиле Эрудит.

Если я не ошибаюсь, ваши символы подстановки нужно будет интерпретировать строго как m/./.

Динамические символы

Не могу сейчас придумать какое-либо значительно лучшее решение, чем использовать регулярное выражение для своего набора слов.

...