Создание древовидной структуры данных - PullRequest
Новая
       33

Создание древовидной структуры данных

3 голосов
/ 21 мая 2011

У меня есть некоторые данные: 

A
AXNHJNEHWXNOECMEJK
DNFJNXYEEQWhsdbchjsxs
XMJQWsdsEOJdfsKMDJE

....

Каждая строка - это массив, а каждая буква - объект.У меня есть функция сравнения, которая может сказать, что буква А эквивалентна букве а (на самом деле это не буква. Это русские слова и функция сравнения используют морфологию, чтобы дать мне знать, что слова равны, например, матрешка == матрешки == матрешкины и массивырусские предложения. Например: "Мама мыла раму").Я хочу создать древовидную структуру данных, которая выглядит следующим образом: 

1) A
2.1) BA
2.2) DHBAFH
3.1) BEDMEWA
etc...

В противном случае дочерние узлы должны содержать буквы из родительских узлов.Если вы знаете, как работать Google AdWords, я думаю, вы можете понять меня.Мой вопрос, как сделать это БЫСТРО.Мне нужно создать дерево с тысячами массивов.Функция сравнения работает очень медленно (использует большой словарь), поэтому скорость - это реальная проблема.

Некоторые простые данные (извините за русский):

вот набор предложений 

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

мы должны создать следующую древовидную структуру данных 

1) сайты
1->2.1) сайты недорого
1->2.2) сайты дешево
1->2.3) красивый сайт по доступным ценам 
1->2.2->3) сайты дешево и быстро

другие родительские узлы: 

1) хочу купить хороший стул 
1) стул по доступным ценам

Дочерние узлы должны содержать больше слов, чем родительские.

Ответы [ 2 ]

1 голос
/ 22 мая 2011

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

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

Когда узел совпадает, добавьте к нему предложение.Если предложение не соответствует ни одному узлу, сделайте его родительским узлом.

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

1 голос
/ 21 мая 2011

Ну

Похоже, эта ссылка может помочь вашей проблеме

Быстрый поиск строки с суффиксными деревьями: http://marknelson.us/1996/08/01/suffix-trees/

и

Суффикс дерево

http://en.wikipedia.org/wiki/Suffix_tree

...