Как сравнить и сохранить строки в базе данных строк, для общих комбинаций?

Question

У меня есть целая куча строк фиксированной длины (длиной около 100 символов в каждой), которые я хочу сравнить друг с другом, чтобы найти наиболее распространенные комбинации символов между всеми строками.

Что будетхороший способ сравнить каждую новую строку с базой данных уже собранных строк?И что тогда будет хорошим способом сохранить результаты и строку в базе данных?Какая структура данных подойдет для этого?

Я пометил вопрос "ruby", но я думаю, что он довольно общий, поэтому ищу что-то действительно.

Answer 1

Если вы имеете в виду, что для этих 3 строк:

а BCD CDE

вы хотите получить следующий вывод:

a   - 1
b   - 2
c   - 3
d   - 2
e   - 1
ab  - 1
bc  - 2
cd  - 2
de  - 1
abc - 1
bcd - 1
cde - 1

Тогда я бы рекомендовал TRIE (http://en.wikipedia.org/wiki/Trie), и хранить количество появлений каждой группы символов в ее узлах (добавляя 1 для каждого нового найденного соответствия).

Тогда алгоритм может быть довольно простым

Начните с 'abc' и, пока вы пересекаете дерево (необязательно создавая новые узлы), добавьте 1 к каждому посещенному узлу, затем продолжите с 'bc' и затем с 'c'. И то же самое с «BCD». Перейти на «bcd», «CD», «D»

Обходя дерево и добавляя 1 к каждому посещенному узлу, вы должны покрыть все двойные, тройные и т. Д.

Надеюсь, это поможет, Резна