0

Задача: Есть предложения и нужно получить список похожих слов.

Пробовал вот такой путь, но он не эффективен:

Я удаляю всю пунктуацию и делю все на слова, деля по пробелу.

В итоге у меня получается ~170 000 уникальных слов.

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

Однако, сравнивая слова между собой-это где-то 170 000^2 итераций => долго.

Как можно повысить эффективность?

10
  • приведите слово в lowercase, там останутся только буквы (латинские?) в нижнем регистре. Создайте массив из 26 (для латиницы) элементов для каждого слова, храните в этом массиве счетчики количества каждой буквы в слове. Сравнением 2 слов станет сравнение 2 массивов по 26 элементов, Левенштейна применяйте если, например, счетчики букв отличаются на 2, например - это ументшит стоимость одного сравнения
    – tym32167
    10 окт 2018 в 15:17
  • Чтобы уменьшить количество сравнений, я бы отсортировал строки чем то типа этого - сортировка выполняется линейно
    – tym32167
    10 окт 2018 в 15:21
  • предполагая, что похожие слова начинаются одинаково, то в отсортированном массиве они должны быть рядом. Хотя я могу быть и не прав - зависит от того, что вы понимаете под похожими словами
    – tym32167
    10 окт 2018 в 15:22
  • Можно ещё придумать что то, но оно будет зависеть от специфики языка
    – tym32167
    10 окт 2018 в 15:24
  • Попробую исключить сравнение слишком длинных с короткими. А так же на основании частоты встречаемости предполагать, что тот или иной случай не ошибочный. Ещё попробую как вы сказали сравнивать только те, что начинаются на одну букву так как вероятность ошибки крайне мала. По идее, таким образом сравниваемая выборка будет меньше.
    – iluxa1810
    10 окт 2018 в 16:34

0

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Посмотрите другие вопросы с метками или задайте свой вопрос.