查找字符串中所有重复的子字符串以及它们出现的频率
Finding all repeated substrings in a string and how often they appear
问题：
我需要满足以下条件的所有字符序列：
- 字符序列必须出现多次（(LE, 1) 因此无效）。
- 字符序列必须长于一个字符（因此 (M, 2) 无效）。
- 字符序列不能是出现相同次数的较长现有序列的一部分（因此，如果 (LIO, 2) 存在，则 (LI, 2) 无效）。
所以，如果输入字符串是：KAKAMNENENELIOLELIONEM$
输出将是：
(KA, 2)
(NE, 4)
(LIO, 2)
它还需要快，它应该能够在合理的时间内解决 1000 个字符长的字符串。
我尝试过的：
从后缀树中获取分支数量：
编辑this后缀树-创建库（Python-Suffix-Tree），我制作的程序给出了一些错误的结果。
我在 suffix_tree.py 中将此函数添加到 SuffixTree class:
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() 基本上遍历节点之间的所有连接（在本库中称为边）并保存它指向的节点还有多少连接（将其保存到 repeated_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:
（无法完成）
问题：
我怎样才能制作出我想要的程序？
你的后缀树方法是正确的方法。
获取匹配集及其出现次数
基本上您需要做的是以 BFS 方式遍历树。从根的 children 开始，您将递归地计算每个节点可到达的叶数。这将导致 Node 的方法，您将在根上调用该方法。这是一个可能的实现：
def count_leaves(self, stree):
leaves_count = 0
for child in [stree.nodes[x.dest_node_index] for x in self.edges.values()]:
child_leaves_count = child.count_leaves(stree)
if 0 == child_leaves_count:
# The child node is a leaf...
leaves_count = leaves_count + 1
else:
# The child node is an internal node, we add up the number of leaves it can reach
leaves_count = leaves_count + child_leaves_count
self.leaves_count = leaves_count
return leaves_count
现在，每个节点都标有它可以到达的叶数。
然后，后缀树的有趣属性将帮助您自动过滤掉不符合您的某些要求的子字符串：
- 如果一个字符串只出现一次，那么您必然会过渡到叶节点（所述过渡至少有两个字符，因为我们不计算结束标记
$）。这意味着它不是一个明确的状态，因此我们甚至不考虑它。
- 如果我们有(LI, 2) 和(LIO, 2)，那么(LI, 2) 是后缀树的隐式状态，这意味着它在一条边的中间。由于我们只考虑具有显式状态的子串（即在节点中结束），我们永远不会找到 (LI, 2) 开头。
- 内部节点至少有2个children，否则它们就是一片叶子并且有none.
现在遍历内部节点将获得子字符串列表及其在输入字符串中出现的次数（您需要过滤掉表示 1 个字符子字符串的节点）。
您将在下面找到输入字符串的后缀树的字符串表示形式。这将帮助您可视化匹配的子字符串。
- O - N E M $ - ##
- L E L I O N E M $ - ##
- I O - N E M $ - ##
- L E L I O N E M $ - ##
- $ - ##
- E - M $ - ##
L I O - N E M $ - ##
L E L I O N E M $ - ##
N E - L I O L E L I O N E M $ - ##
N E L I O L E L I O N E M $ - ##
- K A - M N E N E N E L I O L E L I O N E M $ - ##
K A M N E N E N E L I O L E L I O N E M $ - ##
- L - E L I O N E M $ - ##
I O - N E M $ - ##
L E L I O N E M $ - ##
- A - M N E N E N E L I O L E L I O N E M $ - ##
K A M N E N E N E L I O L E L I O N E M $ - ##
- M - $ - ##
N E N E N E L I O L E L I O N E M $ - ##
- N E - M $ - ##
L I O L E L I O N E M $ - ##
N E - L I O L E L I O N E M $ - ##
N E L I O L E L I O N E M $ - ##
这将导致以下输出：
(IO, 2)
(ELIO, 2)
(ENE, 2)
(KA, 2)
(LIO, 2)
(NE, 4)
(NENE, 2)
排除固定次数 (N) 的冗余匹配
我们现在假设 LIO 和 IO 应该被过滤掉，因为就像 ELIO 一样，它们有两个匹配项。较大匹配的此类子字符串将称为 "redundant matches"。以下谜题仍未解决：给定恰好出现 N 次 a.k.a N-matches 的所有匹配集（其中 N 是固定整数），我们如何过滤"redundant" 个？
我们首先从 N-matches 的集合中创建一个按长度递减排序的优先级队列。然后，我们将迭代地构建这些匹配项的 广义后缀树 (GST) 以识别 冗余匹配项 .为此，算法如下：
- 对于堆中的每个元素（取自顶部），测试该元素是否是已在 GST 中注册的元素之一的子串
- 如果不是：将其插入 GST 并将其附加到 "good matches".
的列表中
- 否则：跳过它，因为另一个更大的匹配项已经注册...并尝试下一个元素
- 一旦堆为空，匹配列表将包含所有 non-redundant N-matches.
这导致以下伪 Python 代码：
match_heap = heapify(set_of_matches)
good_matches = []
match_gst = generalized_suffix_tree()
while (not match_heap.empty()):
top_match = match_heap.top()
if (not match_gst.is_substring(top_match.string)):
gst_match.insert(top_match.string)
good_matches.append(top_match)
else:
# The given match is a substring of an already registered, bigger match
# We skip it
return good_matches
过滤所有冗余匹配项
现在我们可以过滤 N-matches 的冗余匹配项，很容易从我们的全局匹配集中过滤掉所有这些匹配项。我们使用它们的出现次数将匹配项收集到桶中，然后我们在每个桶上应用上一节的算法。
备注
要实现上述算法，您需要有一个广义后缀树实现，这与常规后缀树有点不同。如果找不到 Python 实现，您可以随时调整现有的实现。请参阅 以获取有关如何执行此操作的提示。
问题：
我需要满足以下条件的所有字符序列：
- 字符序列必须出现多次（(LE, 1) 因此无效）。
- 字符序列必须长于一个字符（因此 (M, 2) 无效）。
- 字符序列不能是出现相同次数的较长现有序列的一部分（因此，如果 (LIO, 2) 存在，则 (LI, 2) 无效）。
所以，如果输入字符串是：KAKAMNENENELIOLELIONEM$
输出将是：
(KA, 2)
(NE, 4)
(LIO, 2)
它还需要快，它应该能够在合理的时间内解决 1000 个字符长的字符串。
我尝试过的：
从后缀树中获取分支数量：
编辑this后缀树-创建库（Python-Suffix-Tree），我制作的程序给出了一些错误的结果。
我在 suffix_tree.py 中将此函数添加到 SuffixTree class:
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() 基本上遍历节点之间的所有连接（在本库中称为边）并保存它指向的节点还有多少连接（将其保存到 repeated_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:
（无法完成）
问题：
我怎样才能制作出我想要的程序？
你的后缀树方法是正确的方法。
获取匹配集及其出现次数
基本上您需要做的是以 BFS 方式遍历树。从根的 children 开始，您将递归地计算每个节点可到达的叶数。这将导致 Node 的方法，您将在根上调用该方法。这是一个可能的实现：
def count_leaves(self, stree):
leaves_count = 0
for child in [stree.nodes[x.dest_node_index] for x in self.edges.values()]:
child_leaves_count = child.count_leaves(stree)
if 0 == child_leaves_count:
# The child node is a leaf...
leaves_count = leaves_count + 1
else:
# The child node is an internal node, we add up the number of leaves it can reach
leaves_count = leaves_count + child_leaves_count
self.leaves_count = leaves_count
return leaves_count
现在，每个节点都标有它可以到达的叶数。
然后，后缀树的有趣属性将帮助您自动过滤掉不符合您的某些要求的子字符串：
- 如果一个字符串只出现一次，那么您必然会过渡到叶节点（所述过渡至少有两个字符，因为我们不计算结束标记
$）。这意味着它不是一个明确的状态，因此我们甚至不考虑它。 - 如果我们有(LI, 2) 和(LIO, 2)，那么(LI, 2) 是后缀树的隐式状态，这意味着它在一条边的中间。由于我们只考虑具有显式状态的子串（即在节点中结束），我们永远不会找到 (LI, 2) 开头。
- 内部节点至少有2个children，否则它们就是一片叶子并且有none.
现在遍历内部节点将获得子字符串列表及其在输入字符串中出现的次数（您需要过滤掉表示 1 个字符子字符串的节点）。
您将在下面找到输入字符串的后缀树的字符串表示形式。这将帮助您可视化匹配的子字符串。
- O - N E M $ - ##
- L E L I O N E M $ - ##
- I O - N E M $ - ##
- L E L I O N E M $ - ##
- $ - ##
- E - M $ - ##
L I O - N E M $ - ##
L E L I O N E M $ - ##
N E - L I O L E L I O N E M $ - ##
N E L I O L E L I O N E M $ - ##
- K A - M N E N E N E L I O L E L I O N E M $ - ##
K A M N E N E N E L I O L E L I O N E M $ - ##
- L - E L I O N E M $ - ##
I O - N E M $ - ##
L E L I O N E M $ - ##
- A - M N E N E N E L I O L E L I O N E M $ - ##
K A M N E N E N E L I O L E L I O N E M $ - ##
- M - $ - ##
N E N E N E L I O L E L I O N E M $ - ##
- N E - M $ - ##
L I O L E L I O N E M $ - ##
N E - L I O L E L I O N E M $ - ##
N E L I O L E L I O N E M $ - ##
这将导致以下输出：
(IO, 2)
(ELIO, 2)
(ENE, 2)
(KA, 2)
(LIO, 2)
(NE, 4)
(NENE, 2)
排除固定次数 (N) 的冗余匹配
我们现在假设 LIO 和 IO 应该被过滤掉，因为就像 ELIO 一样，它们有两个匹配项。较大匹配的此类子字符串将称为 "redundant matches"。以下谜题仍未解决：给定恰好出现 N 次 a.k.a N-matches 的所有匹配集（其中 N 是固定整数），我们如何过滤"redundant" 个？
我们首先从 N-matches 的集合中创建一个按长度递减排序的优先级队列。然后，我们将迭代地构建这些匹配项的 广义后缀树 (GST) 以识别 冗余匹配项 .为此，算法如下：
- 对于堆中的每个元素（取自顶部），测试该元素是否是已在 GST 中注册的元素之一的子串
- 如果不是：将其插入 GST 并将其附加到 "good matches". 的列表中
- 否则：跳过它，因为另一个更大的匹配项已经注册...并尝试下一个元素
- 一旦堆为空，匹配列表将包含所有 non-redundant N-matches.
这导致以下伪 Python 代码：
match_heap = heapify(set_of_matches)
good_matches = []
match_gst = generalized_suffix_tree()
while (not match_heap.empty()):
top_match = match_heap.top()
if (not match_gst.is_substring(top_match.string)):
gst_match.insert(top_match.string)
good_matches.append(top_match)
else:
# The given match is a substring of an already registered, bigger match
# We skip it
return good_matches
过滤所有冗余匹配项
现在我们可以过滤 N-matches 的冗余匹配项，很容易从我们的全局匹配集中过滤掉所有这些匹配项。我们使用它们的出现次数将匹配项收集到桶中，然后我们在每个桶上应用上一节的算法。
备注
要实现上述算法，您需要有一个广义后缀树实现，这与常规后缀树有点不同。如果找不到 Python 实现，您可以随时调整现有的实现。请参阅