标签: suffix-tree

这是一个面试问题:

给定一个字符串,找到它在字典中的单词的所有排列.

我的解决方案

将字典的所有单词放入后缀树中,然后搜索树中字符串的每个排列.

搜索时间是O(n),n字符串的大小在哪里.但字符串可能有n!排列.

如何提高效率？

我是python的新手,我开始使用后缀树.我可以构建它们,但是当字符串变大时我遇到了内存问题.我知道它们可以用于处理大小为4 ^ 10或4 ^ 12的DNA字符串,但每当我尝试实现一种方法时,我最终会遇到内存问题.

这是我生成字符串和后缀树的代码.

import random

def get_string(length):
    string=""
    for i in range(length):
        string += random.choice("ATGC")
    return string

word=get_string(4**4)+"$"

def suffixtree(string):
    for i in xrange(len(string)):
        if tree.has_key(string[i]):
            tree[string[i]].append([string[i+1:]][0])
        else:
            tree[string[i]]=[string[i+1:]]
    return tree

tree={}
suffixtree(word)

当我达到4**8左右时,我遇到了严重的内存问题.我对此很陌生,所以我肯定我错过了保存这些东西的东西.任何建议将不胜感激.

作为注释:我想进行字符串搜索以在非常大的字符串中查找匹配的字符串.搜索字符串匹配大小为16.因此,这将在大字符串中查找大小为16的字符串,然后移动到下一个字符串并执行另一个搜索.由于我将进行大量搜索,因此建议使用后缀树.

非常感谢

我正在阅读"算法设计手册"中的数据结构章节,并遇到了后缀树.

该示例说明:

输入:

XYZXYZ$
 YZXYZ$
  ZXYZ$
   XYZ$
    YZ$
     Z$
      $

输出:

我无法理解从给定的输入字符串生成该树的方式.后缀树用于在给定的字符串中查找给定的子字符串,但给定的树如何帮助它呢？我确实理解下面显示的另一个trie示例,但如果下面的trie被压缩到后缀树,那么它会是什么样子？

我有大约3,500个由单行字符串组成的文件.文件大小不一(从大约200b到1mb).我正在尝试将每个文件与其他文件进行比较,并找到两个文件之间长度为20个字符的公共子序列.请注意,子序列仅在每次比较期间在两个文件之间是通用的,并且在所有文件中不常见.

我已经解决了这个问题,因为我不是专家,所以我最终得到了一些临时解决方案.我使用itertools.combinations在Python中构建一个列表,最终得到大约6,239,278个组合.然后,我将这两个文件一次传递给Perl脚本,该脚本充当用C编写的后缀树库的包装器,称为libstree.我试图避免这种类型的解决方案,但Python中唯一可比较的C后缀树包装器遭受内存泄漏.

所以这是我的问题.我已经计时了,在我的机器上,该解决方案在25秒内处理了大约500次比较.这意味着,完成任务需要大约3天的连续处理.然后我必须再做一遍看看25个字符而不是20个.请注意我已经离开了我的舒适区并且不是一个非常好的程序员,所以我确信有一个更优雅的方式去做这个.我以为我会在这里问它并生成我的代码,看看是否有人建议我如何更快地完成这项任务.

Python代码:

from itertools import combinations
import glob, subprocess

glist = glob.glob("Data/*.g")
i = 0

for a,b in combinations(glist, 2):
    i += 1
    p = subprocess.Popen(["perl", "suffix_tree.pl", a, b, "20"], shell=False, stdout=subprocess.PIPE)
    p = p.stdout.read()
    a = a.split("/")
    b = b.split("/")
    a = a[1].split(".")
    b = b[1].split(".")
    print str(i) + ":" + str(a[0]) + " --- " + str(b[0])
    if p != "" and len(p) == 20:
        with open("tmp.list", "a") as openf: …

我已经看了这个问题,但我仍然没有看到后缀树和Trie之间的区别.

两者都具有给定字符串的所有子字符串,因此它们彼此之间有何不同？

我看到了维基百科页面,但仍然不清楚这个想法.

为了找到2个字符串(T和S)中最长的公共子字符串,我读过我们必须为字符串构建一个后缀树T($1)S($2),其中`($ 1)和($ 2)是不属于字符串的特殊字符.

但对于字符串维基百科的图像ABAB和BABA看起来是这样的:

为什么它不包含整个字符串ABAB($1)BABA($2)？它不是连接字符串的后缀吗？

叶子上的数字是多少？

我需要为最长的两个模式前缀/后缀匹配编码算法,其时间复杂度为O(n + m1 + m2),其中n是String的长度,m1,m2分别是pattern1和pattern2的长度.

示例:如果字符串为"OBANTAO"且Pattern1为"BANANA"且Patten2为"SIESTA",则答案为字符串的子字符串"BANTA",其由BANANA的前缀BAN和SIESTA的后缀TA组成.

谷歌的结果是:"Rabin-karp字符串搜索算法","Knuth-morris-pratt算法"和"Boyer-moore字符串搜索算法".

我能够理解以上所有3种算法,但问题在于,它们都基于"单一模式前缀/后缀匹配".我无法为两个模式前缀/后缀匹配扩展它们.

一个示例算法或搜索它的链接对我开发程序非常有帮助.

我正在寻求澄清jogojapan对这个问题的回答:Ukkonen的后缀树算法用简单的英语？

有人可以澄清以下内容:在上一次触摸active_point的步骤6中,它被设置为(root, 'x', 0)(但是在此时不存在以'x'开头的边缘).下一次引用活动点是在步骤7中,好像它已经== (root, **'a'**, 0)因为确定了(使用active_point？)后缀'a'已经在树中,并且只需要增加active_length,所以步骤7结束时的active_point变为(root, 'a', 1).

active_point如何从(root, 'x', 0)步骤6更改(root, 'a', 0)为步骤7？

我无法理解构造后缀树的最坏情况时间复杂性是如何线性的 - 特别是当我们需要为可能由重复单个字符组成的字符串构建后缀树时,例如"aaaaa".

即使我要为"aaaaa"构造一个压缩后缀树,我也无法真正压缩任何节点,因为从节点开始的两个边都不能有以相同字符开头的字符串标签.

这将导致高度为5的后缀树,并且在每次插入后缀时,我将需要保持从根到叶的遍历.

这是我接近的方式:后缀:a,aa,aaa,aaaa,aaaaa

创建根节点,创建一个带有'a'的边缘并将其连接到一个新节点,其左边带有"$",并重复此过程直到我们可以aaaaa.

这将导致O(n ^ 2)而不是O(n).我在这里错过了什么？

给定两个字符串，我想从最长到最短识别所有常见的子字符串。

我想删除任何“子”子字符串。例如，“1234”的任何子字符串都不会包含在“12345”和“51234”之间的匹配中。

string1 = '51234'

string2 = '12345'

result = ['1234', '5']

我想找到最长的公共子串，然后递归地找到左边/右边的最长子串。但是，我不想在找到后删除公共子字符串。例如，下面的结果在中间共享一个 6：

string1 = '12345623456'

string2 = '623456'

result = ['623456', '23456']

最后，我需要根据数千个字符串的固定列表检查一个字符串。我不确定是否可以采取一个聪明的步骤来散列这些字符串中的所有子字符串。

以前的答案：

在这个线程中，找到了一个需要 O(nm) 时间的动态规划解决方案，其中 n 和 m 是字符串的长度。我对使用后缀树的更有效方法感兴趣。

背景：

我正在从旋律片段中创作歌曲旋律。有时，组合会设法生成与现有音符的一行中太多音符匹配的旋律。

我可以使用字符串相似性度量，例如编辑距离，但相信与旋律差异很小的曲调是独特而有趣的。不幸的是，这些曲调与连续复制旋律的许多音符的歌曲具有相似的相似度。