Как посчитать количество повторяющихся букв (отрезков) в наборе слов?

Question

[Алексей Николаев]

Добрый вечер всем.
Есть нетривиальная задача - нужно из массива слов выделить те, у которых повторяется начало, т.е. посчитать слова, которые имеют больше всего вероятности семантической сходности. Например, "автострада" и "автомобиль" попадут в конечную выдачу. Это можно сделать несколькими вложенными циклами (циклы вообще заменяют почти любой алгоритм), но красота и скорость такого решения стоит под огромным сомнением...

Как бы попробовали реализовать нечто эдакое вы?.. Как вообще можно такое реализовать (может, существуют известные алгоритмы)? Буду благодарен за советы, спасибо.

P.S. библиотеки (вроде phpMorphy) возможны, но нежелательны

Comments

[mamba2013]

openkontent.ru

Answer 1

[Заур Ашурбеков]

если массив слов большой, предлагаю создать ориентированные деревья, узлом которой будет буква, вершина - первая буква слова, во втором уровне будут вторые буквы и т.д. до конца всех слов. И количество сходностей можно будет определить количеством узлом, уровень сходности - уровнем узла. Пример:
Слова Автострада, Автомобиль Авиация
Граф:

А - В - Т - О - С - Т - Р - А - Д - А
    |       |
    И       М - О - Й - К - А
    |       |
    А       О
    |       |
    Ц       Б
    |       |
    И       И
    |       |
    Я       Л
            |
            Ь

Такие деревья надо создать для каждой буквы, с которой начинаются слова в словаре

Answer 2

[Rsa97]

Угу. Туда же попадут "автор", "автохтон", "автобиография", "автомат"... А уж слова с приставками... По хорошему, надо разделять слова на приставку, корень (корни), суффикс и окончание, для чего желательно знать, как минимум роль слова в предложении (и то может не помочь, попробуйте разобрать "Косил косой косой косой" - да, тот самый заяц на поляне, да ещё и коса кривая.
Но если так хочется - строите дерево, где каждый уровень - следующая буква слова, а в узлах и листьях стоят счётчики количества слов. Для слов "автомобиль", "авто" и "автострада" получаем:

.                   +-м(1)-о(1)-б(1)-и(1)-л(1)-ь(1)
.а(3)-в(3)-т(3)-о(3)+
.                   +-с(1)-т(1)-р(1)-а(1)-д(1)-а(1)

Затем обходим дерево, там где сумма счётчиков в дочерних узлах не равна счётчику в родительском - заканчивается слово, а разность между суммами даёт количество этих слов в тексте.

Answer 3

[Илья Плотников]

Возможно, следует использовать sphinx?

Comments

[Илья Плотников]

Или preg_match_all и подсчет результатов

Answer 4

[Mnobody]

Сдесь описывается немного другая задача, но может натолкнет на какие-то идеи (если хочется разбираться в вопросе).
habrahabr.ru/post/190694
Еще можете погуглить стиммеры и лематизаторы.