Проблема:
Мне нужны все последовательности символов, которые соответствуют следующему:
- Последовательность символов должна присутствовать более одного раза (поэтому (LE, 1) недопустимо).
- Последовательность символов должна быть длиннее одного символа ((M, 2) недопустимо).
- Последовательность символов не должна быть частью более длинной существующей последовательности, которая присутствует такое же количество раз (таким образом, (LI, 2) недопустимо, если присутствует (LIO, 2)).
Таким образом, если бы входная строка была: KAKAMNENENELIOLELIONEM$, на выходе было бы:
(KA, 2)
(NE, 4)
(LIO, 2)
Он также должен быть быстрым, он должен иметь возможность решить строку длиной 1000 символов за разумное время.
Что я пробовал:
Получение количества ветвей из суффиксного дерева:
Редактирование этого суффиксного дерева -создание библиотеки (Python-Suffix -Tree), я сделал программу, которая дает несколько ошибочные результаты.
Я добавил эту функцию в класс SuffixTree в suffix_tree.py:
def get_repeated_substrings(self):
curr_index = self.N
values = self.edges.values()
values = sorted(values, key=lambda x: x.dest_node_index)
data = [] # index = edge.dest_node_index - 1
for edge in values:
if edge.source_node_index == -1:
continue
top = min(curr_index, edge.last_char_index)
data.append([edge.source_node_index,
self.string[edge.first_char_index:top+1]])
repeated_substrings = {}
source_node_indexes = [i[0] for i in data]
nodes_pointed_to = set(source_node_indexes)
nodes_pointed_to.remove(0)
for node_pointed_to in nodes_pointed_to:
presence = source_node_indexes.count(node_pointed_to)
key = data[node_pointed_to-1][1]
if key not in repeated_substrings:
repeated_substrings[key] = 0
repeated_substrings[key] += presence
for key in repeated_substrings:
if len(key) > 1:
print(key, repeated_substrings[key])
А затем использовал его и остальную часть библиотеки следующим образом:
from lib.suffix_tree import SuffixTree
st = SuffixTree("KAKANENENELIOLELIONE$")
print(st.get_repeated_substrings())
Выход:
KA 2
NE 7
LIO 2
IO 4
get_repeated_substrings() в основном проходит через все соединения между узлами (называемые ребрами в этой библиотеке) и сохраняет, сколько еще соединений имеет узел, на который он указывает (он сохраняет его в Repeat_substrings), а затем печатает сохраненные значения, которые содержат более одного символа. длинная.
Он добавляет количество подключений к количеству, которое уже было для этой последовательности, что работает большую часть времени, но, как вы можете видеть в приведенном выше выводе, это привело к неправильному значению для «NE» (7, должно было быть 4). После решения этой проблемы я понял, что этот метод не будет обнаруживать паттерны, составленные из одного и того же символа (AA, BB), и другие неисправности. Мой вывод: либо с суффиксными деревьями никак не решить, либо я что-то очень неправильно делаю.
Другие методы:
Я также пробовал несколько более простых способов, состоящих из перебора вещей, но это тоже не увенчалось успехом:
import copy
string = 'kakabaliosie'
for main_char in set(string):
indices = []
for char_i, char in enumerate(string):
if main_char == char:
indices.append(char_i)
relative = 1
while True
for index in indices:
other_indices = copy.deepcopy(indices)
other_indices.remove(index)
for other_index in other_indices:
(не успеваю закончить)
ELIOможет быть найдена дважды, но не указана в результатах. То же самое дляENE, у которых есть два перекрывающихся совпадения. - person Rerito schedule 23.06.2016