查找字符串中所有重复的子字符串以及它们出现的频率

Question

问题：

我需要满足以下条件的所有字符序列：

1. 字符序列必须出现多次（(LE, 1) 因此无效）。
2. 字符序列必须长于一个字符（(M, 2) 因此无效）。
3. 字符序列不能是存在相同次数的更长的现有序列的一部分（如果 (LIO, 2) 存在，则 (LI, 2) 因此无效）。

因此，如果输入字符串是：KAKAMNENENELIOLELIONEM$ 输出将是：

(KA, 2)
(NE, 4)
(LIO, 2)

它还需要很快，它应该能够在合理的时间内解决 1000 个字符的长字符串。

我尝试过的：

从后缀树获取分支数量：

编辑此后缀树-创建库（Python-Suffix-Tree），我制作了一个程序，该程序给出了一些错误的结果。

我将此函数添加到 suffix_tree.py 中的 SuffixTree 类：

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:

（无法完成它）

题：

我怎样才能做一个程序来做我想要的？

Answer 1

您的后缀树方法是正确的方法。

获取匹配集及其出现次数

基本上你需要做的是以 BFS 方式遍历树。从根的孩子开始，您将递归计算每个节点可到达的叶子数。这将导致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 个孩子，否则它们将是一个叶子并且没有。

现在迭代内部节点将为您提供子字符串列表及其在输入字符串中的出现次数（您需要过滤掉代表 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，它们有两个匹配项。较大匹配的此类子串将称为“冗余匹配”。下面的难题仍未解决：给定恰好发生 N 次的所有匹配集合，即N 匹配（其中 N 是固定整数），我们如何过滤掉“冗余”匹配？

我们首先从按长度递减排序的一组 N 匹配中创建一个优先级队列。然后我们将迭代地构建这些匹配的广义后缀树( GST ) 以识别冗余匹配。为此，算法如下：

1. 对于堆中的每个元素（取自顶部），测试该元素是否是已在GST 中注册的元素之一的子字符串
   • 如果不是：将其插入GST并将其附加到“良好匹配”列表中。
   • 其他：跳过它，因为已经注册了另一个更大的匹配......并尝试使用下一个元素
2. 一旦堆为空，好的匹配列表将包含所有非冗余 N 匹配。

这导致以下伪 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 实现，你总是可以调整你得到的那个。请参阅此问题以获取有关如何执行此操作的提示。