1回答
是否有任何工具或实用工具或perl/python脚本能够在大型文本文件中找到最长的重复子字符串并打印这些模式和每种模式发生的次数？
浏览 1提问于2010-01-27得票数 5
1回答
背景(简化)
我得到了很多由第三方自动生成的文件(比如几个不同地址合并的输出)，我正在尝试以编程方式从其中恢复原始模板和地址/自定义数据。
我到目前为止看过的东西，
有大量的库(jsdiff，difflib)来区分两个文件。我发现这样做很有帮助，可以计算出更改的%单词，这是一个很好的指示，如果两个文件来自同一个模板
问题
因此，现在我正处于将相似的文本文件组合在一起的阶段，现在我最好能找到一种区分所有这些文件的方法，将相同的文本与不同的文本区分开来：
Hello [Mr, Mrs] [NameA, NameB, NameC...], we are pleased to (...)
那么，如何在
浏览 3提问于2016-06-03得票数 3
2回答
两个密切相关的数据结构是后缀树和后缀数组。据我所知，后缀树比后缀数组更快、更强大、更灵活、更节省内存。然而，在中，最热门的答案之一提到后缀数组在实践中得到了更广泛的使用。我没有任何使用这两种结构的经验，但是现在我似乎总是更喜欢后缀树而不是后缀数组，以解决需要它们提供的功能的问题(例如，快速的子串检查)。
在什么情况下，后缀数组比后缀树更可取？
(顺便说一句，虽然这个问题与我链接的那个问题有关，但我不认为它是完全相同的，因为我只对后缀数组和后缀树的比较感兴趣，完全不考虑尝试。但是，如果您不同意，我可以理解这个问题是否应该结束。)
浏览 3提问于2011-08-21得票数 2
回答已采纳
我遇到了一个问题，它需要一个包含字符串S的数据结构，并允许我：
检查单词W是否是O中S的一个子词
查找最长的S后缀，它也是O( time )时间中给定单词U的前缀
在S的末尾添加字符串K，以O( the )时间为单位
我发现由Ukkonen算法构造的是我正在寻找的。算法被描述为，而我的“在线”部分有一个问题:在插入每个字符后，算法构建一个隐式后缀树，该树可以在最后一步转换为显式。但是，如果我想在这一步之前使用隐式树进行搜索呢？"online“表示在插入分析字符串的任何前缀后是可能的，但我找不到任何在隐式树上操作的最简单算法的例子。
我的问题是:如何在隐式后缀树中搜索
浏览 3提问于2013-01-11得票数 3
回答已采纳
def solution(S):
total = 0
i = 1
while i <= len(S):
for j in range(0, len(S) - i + 1):
if is_p(S[ j: j + i]):
total += 1
i += 1
return total
def is_p(S):
if len(S) == 1:
return False
elif S == S[::-1]:
return Tru
浏览 29提问于2018-05-31得票数 0
1回答
我使用了来理解前缀trie (虽然最终我试图找到后缀trie )，但是到示例代码的链接被打破了，所以我从视频中得到了这个，有两个函数，即插入和搜索，如下所示
void insert(string word)
{
node* current=head;
current->prefix_count++;
for(unsigned int i=0;i<word.length();++i)
{
int letter=(int)word[i]-(int)'a';
if (current->child[l
浏览 3提问于2016-04-11得票数 1
回答已采纳
4回答
我是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)+&
浏览 0提问于2012-04-10得票数 5
回答已采纳
3回答
我已经寻找了很长一段时间关于后缀树的教程。因此，我发现了两个关于理解后缀树的帖子：，。
但我不能说我知道怎么做，哦。在Skiena的“算法设计手册”中，他说：
由于线性时间后缀树构造算法是非平凡的，我建议使用现有的实现。
那么，后缀树的在线构造算法有那么难吗？谁能让我朝着正确的方向去理解它？
总之，切入主题，除了建筑，还有一件事我不懂后缀树。因为后缀树中的边只是一对整数(对吗？)指定子字符串的开始和结束位置，如果我想在这个后缀树中搜索字符串x，我应该如何做呢？取消引用后缀树中的整数，然后逐个与x进行比较？不可能是这样的。
浏览 6提问于2012-03-05得票数 20
回答已采纳
2回答
1973年，Weiner首次给出了后缀树的线性时间结构。该算法在1976年由McCreight简化，并在1995年由Ukkonen简化。然而，我发现Ukkonen的算法在概念上相对复杂。
自1995年以来，Ukkonen的算法是否有简化？
浏览 0提问于2012-02-17得票数 3
回答已采纳
1回答
我正在用滚动哈希逻辑实现最长的公共子字符串问题，我无法理解它在O(nlogn) time中是如何工作的。算法指出，
1) choose a length of substring by binary search( low, high, mid)
2) Compute rolling hash values for both strings for a given length mid
3) match the two rolling hashes and see if they are the same and reposition the binary search accordingly
浏览 4提问于2014-01-29得票数 1
回答已采纳
我下载了维基百科文章标题文件，其中包含每一篇维基百科文章的名称。我需要搜索所有可能匹配的文章标题。例如，我可能有“曲棍球”这个词，但我想要的曲棍球的维基百科文章是"Ice_hockey“。它也应该是不区分大小写的搜索。
我使用的是Python，有没有比逐行搜索更有效的方法呢？理想情况下，我会以每分钟500或1000次的速度进行搜索。如果逐行是我唯一的选择，我可以在其中做一些优化吗？
我认为文件中有几百万行。
有什么想法吗？
谢谢。
浏览 0提问于2011-01-30得票数 6
回答已采纳
1回答
后缀树比后缀数组有什么优点？
、、、、
我一直在研究trie、后缀数组和后缀树，我知道这些数据结构可以用于快速查找和更多的应用。现在我的问题是，如果后缀数组比后缀树更适合于后缀数组的情况，那么后缀数组是否具有空间效率和易于实现？
你能列举一下这个人的优势吗？提前谢谢。
浏览 5提问于2017-09-24得票数 0
1回答
我实现了绝对最小广义后缀树构建算法(见下面的代码)。我编写了一个单元测试，它似乎像预期的那样工作(在正确的位置找到正确的子字符串)。但这棵树实在是太大了。问题：，我在什么地方犯了一个错误，还是这种基本形式的后缀树只适用于非常短的文本？
统计
我想用这个搜索大量的文本:多个15-20Mb文本文件，或者像40,000个字符串~60个字符。
当我构建40'000字符串2.5Mb后缀树(如果是一个名称为公司名称的列表)时，该树需要400 if。我可能会优化它大约4倍，但即使这样，它将是超过40个字节的每个字符的原始文本。这正常吗？文献中的估计数字对我来说是很高的。
每株树的平均分枝因子为: 8
浏览 12提问于2018-01-13得票数 0
我试图解决的问题是:我有一百万个单词(多种语言)和一些类别，它们被归类为我的训练语料库。给定单词的测试语料库(数量肯定会随着时间的推移而增加)，我希望在训练语料库中获得这些单词中每个单词的最接近匹配，从而将该单词归类为其最接近匹配的相应类别。
我的解决方案是:最初，我做了这种没有规模的蛮力。现在，我想在训练语料库(O(n))的连接上构建一个后缀树，并查询测试语料库(固定时间)。尝试用python来做这件事。
我正在寻找工具或包，以帮助我开始，或者寻找其他更有效的方法来解决手头的问题。提前谢谢。
编辑1:至于如何找到最接近的匹配，我考虑的是精确匹配对齐的组合(从后缀树中)，然后对于剩余的输入字符
浏览 46提问于2019-06-26得票数 1
假设我有一个集合元组，其元素是N元组，即(xi1, xi2, ... , xin)。
给定元素x = (x1, x2, ..., xn)和y = (y1, y2, ..., yn)，matches(x,y,M)当且仅当x和y的至少M个元素相等。
现在给定一个集合S，matchSet(x,S,M)将返回matches(x,y,M)为true的S的元素。
假设S有这样的数据，matchSet平均只匹配0或1个元素(偶尔会匹配更多，但很少)，有没有一种方法可以编写matchSet并构造S，使它的运行时间与S的大小呈次线性关系，并且它的空间是合理的(即，不将2^L索引放在S上，L是元素的长度)？
或者
浏览 4提问于2016-11-23得票数 2
1回答
在Java中压缩后缀数组
、、、
我已经使用普林斯顿实现创建了一个后缀数组。但是，我的基本文本文档非常非常大，生成的后缀数组的大小超过500mb。有没有办法压缩后缀数组？
谢谢!
浏览 0提问于2012-02-23得票数 2
回答已采纳
2回答
后缀数组与后缀树
、、、、
我只想知道，什么时候后缀树比增强后缀数组优越。
在阅读了之后，我不再看到使用后缀树的理由了。有些方法可能会变得复杂，但您可以使用后缀数组来完成任何事情，使用后缀树所能做的事情，您需要的时间复杂度相同，但内存更少。
一个甚至显示，后缀数组更快，因为它们对缓存更友好，不会产生那么多缓存缺失，然后是后缀树(因此缓存可以更好地预测数组的使用，然后在递归树结构上)。
那么，有谁知道为什么要选择后缀树而不是后缀数组呢？
编辑 Ok，如果您知道更多，请告诉我，到目前为止它：
Suffixarrays阵列不允许在线构造。
一些模式匹配算法在Suffixtree上运行得更快。
(补充)由于在线结构，
浏览 3提问于2012-06-25得票数 17
1回答
Python中是否有一个函数，它返回最长的公共文本子字符串和给定模式的索引，以防该模式必须从该子字符串开始？
text = Lorem ipsum dolor sit amet, consectetur adipisici elit
pattern = amegt
22
浏览 6提问于2015-03-28得票数 0
1回答
我需要设计一种算法，在进程O( n )之后，为m长度的每一个字符串P和1到n之间的k值指定一个n长的T字符串，以检查O(M)<code>E 29</code>时间，如果<code>E 110</code>P出现在T上的k位置<代码>E 211</代码>，仅使用<code>E 112</code>后缀树<code>E 213</code>。
不幸的是，没有任何好的生物信息学书籍与公平的例子和实际的方法。丹·古斯菲尔德的书没有提供解决方案手册。
浏览 4提问于2021-05-04得票数 1
回答已采纳
2回答
给定一个字符串s，在时间复杂度O(|s|)中找到最长的双后缀。
例如:对于字符串banana，LDS为na。对于abaabaa，它是baa。
显然，我考虑过使用后缀树，但我在其中找不到双后缀。
浏览 23提问于2016-07-20得票数 2
1回答
我看过问题，但我仍然看不到后缀树和Trie之间的区别。
两者都有给定字符串的所有子字符串，那么它们之间有什么不同呢？
浏览 6提问于2013-08-01得票数 6
回答已采纳
7回答
哪种结构提供了最佳的性能结果；trie (前缀树)、后缀树还是后缀数组？还有其他类似的结构吗？这些结构的好的Java实现是什么？
编辑:在这种情况下，我希望在一个大型的姓名字典和大量的自然语言文本之间进行字符串匹配，以便在文本上识别字典的名称。
浏览 1提问于2010-03-21得票数 45
回答已采纳
1回答
我在研究生物信息学中的后缀树算法。我想知道这个，后缀树是唯一的吗？
例如，
String str = "xabaxe"
此字符串或其他示例字符串是否有备用后缀树？
浏览 6提问于2014-10-31得票数 2
2回答
我将为给定的字符串实现后缀树，我认为它应该像这样删除
struct suffix
{
char letter;
suffix * left,*right;
};
suffix *insert(suffix *node,char *s){
}
//这里我要用所有出现的子串和字符构建树，但是不知道如何使用左右部分，这棵树是按照严格的字符排序排列的吗?或者?请帮助我，我不想在网上使用一些代码，我需要自己实现它，所以请给我一些提示，一些小代码
浏览 3提问于2012-03-14得票数 2
1回答
我有一个对象的表示，例如SubObjects：H1，H2，F1，F2，其中每个H和F表示一个特定的较小对象。我希望很容易地查询，以检查所有的表示，其中有3个共同的子对象，例如H1,H4,F1,F2将返回，甚至H1,H2,F1,F5。当我查询具有H1、H2、F1、F2三个公共字符串表示部分的对象时。
字符串位置很重要，因此H2、H1、F1、F2不同于H1、H2、F1、F2。
暴力行动计划是不可能的，因为我有数千个这样的字符串要比较。正在考虑通过使用后缀树来解决这个问题。
有没有更有效的数据结构可以用来解决这个问题？
浏览 0提问于2013-03-21得票数 2
回答已采纳
2回答
给定长度为s的字符串n，可以在O(n)中计算s中不同子字符串的数目吗？
示例
输入：abb
输出：5 ('abb', 'ab', 'bb', 'a', 'b')
我已经做了一些研究，但我似乎找不到一种算法能如此有效地解决这个问题。我知道O(n^2)方法是可能的，但是有更有效的算法吗？
我不需要获取每个子字符串，只需要获得不同子字符串的总数(以防有差异)。
浏览 1提问于2016-01-19得票数 8
回答已采纳
1回答
我有一个大约10年的归档文件，这是一个大的目录树结构，在较大的树中的不同位置有较小尝试的多个副本。由于缺乏一致的备份策略和归档策略(基本上都是我自己的错)，这棵树变成了这样的结构。
我正在寻找一种在更大的树中找到完全相同的树副本的方法，这样我就可以删除不需要的副本，让我离清理这一大堆乱七八糟的东西更近一步。
我想我可以编写一个脚本来构建树中文件的数据库，这样我就可以编写另一个脚本来查找相同的树，删除树中嵌套最深的树副本。
然而，就数据库设计和使用哪种算法来有效地比较这些树以找到相同的副本而言，我不确定如何最好地进行这项工作。
简单地说，这是树的样子：
backups/folder1/ back
浏览 0提问于2013-03-03得票数 0
2回答
后缀链接和失败链接有什么区别？
、、、、
这学期我正在学习算法，并且读过关于建立后缀树的和的文章。
我读了这两篇文章，但不能理解这两者的主要基本区别，除了失败链接检查前缀和后缀链接检查后缀。
这两种算法有什么区别？
浏览 1提问于2013-10-19得票数 2
回答已采纳
1回答
一般来说，后缀树被认为比后缀数组的空间效率低。更具体地说，与接近4的后缀数组相比，近似上限O(n)空间效率隐藏了20倍。为什么会发生这种情况？
浏览 8提问于2016-04-06得票数 1
2回答
在关于数据结构的考试中，我确实看到了以下问题：
给出了一个后缀trie。现在，我知道trie只包含指向一系列chars的特定索引的指针。
现在他们声称原来的字符串丢失了，我应该只使用trie找到字符串。我不明白，这怎么可能？
浏览 6提问于2015-03-06得票数 2
回答已采纳
我有两个可观察的集合。
Collection1有一个类型，其中一个成员是字符串(称之为FileName)
Collection2有一个类型，其中一个成员是字符串(称之为ClientID)
文件名中的clientID作为子字符串。因此，ClientID可能是"12345“，文件名可能类似于"OhLookFileFor12345goshdarnit.txt”。我需要找到一种方法将它们映射到一起。第一遍简单的实现如下所示
foreach (var V in Clients)
{
foreach (var Q in aofVM.Organize
浏览 0提问于2014-08-29得票数 0
6回答
我正在读一篇关于Tries的文章，通常被称为前缀树和Suffix Trees。
尽管我找到了用于Trie的代码，但我找不到用于Suffix Tree的示例。此外，我感觉构建Trie的代码与构建Suffix Tree的代码是相同的，唯一的区别是在前一种情况下，我们存储前缀，但在后一种情况下存储后缀。
这是真的吗？有没有人能帮我理清头绪？一个示例代码将会很有帮助！
浏览 0提问于2012-12-16得票数 86
回答已采纳
假设有一个很大的Strings数组。从这个数组中，我只需要得到那些包含特定子字符串的字符串。例如，如果我的数组是String s [] = {"hello world", "back to hell", "say hello world"};，而我的关键字是"hello"，那么它应该返回我的第一个和最后一个元素。我尝试使用KMP和Boyer-Moor算法来检查数组中的每个字符串是否包含子字符串，但这太耗时了。然后我学习了Aho-Corasick算法。我仍然在查找它，但似乎它需要一个子字符串数组和一个大字符串来匹配，而我想要的恰恰相
浏览 4提问于2019-12-24得票数 0
2回答
我正在尝试在hackerrank.com上编写这个问题的代码：
我的代码在小情况下运行得很好，但在大情况下，我的字典很快就会耗尽内存。我能做些什么来解决这个问题？我不想使用列表，因为检查条目是否已经存在将花费太长的时间……下面是我的代码：
n = int(raw_input())
words = []
for x in range(n):
words.append(raw_input())
test = int(raw_input())
queries = []
for x in range(test):
queries.append(raw_input())
dict_o
浏览 2提问于2013-03-19得票数 2
我们可以使用带有后缀树的循环字符串吗？因此，最后一个字符紧跟在列表中的第一个字符之后。
如果是这样的话，这个后缀树的表示与普通的后缀树有什么不同？
浏览 3提问于2012-11-16得票数 3
回答已采纳
NancyFX有内容协商特性，我可以通过实现IResponseProcessor接口为S表达式编写额外的序列化适配器。
有个问题..。S-表情的哑剧类型似乎是text/plain。因此，web服务器无法在text头中确定实际的HTTP_ACCEPT文件类型。
是否有众所周知的做法来决定MIME类型的文本文件？例如,
text/plain+s：添加其文件扩展名
text/plain+s-expression：添加语言名称
浏览 0提问于2019-06-10得票数 0
回答已采纳
1回答
创建SQL智能自动完成的最佳方法
、、、、
我想要创建一个具有智能自动完成功能的联机SQL编辑器。做这件事最好的方法是什么？
如果输入字段为空，则编辑器必须建议选择、INSERT、UPDATE、DELETE<>E29</code>。
如果我输入了以下类型：SELECT * FROM _，编辑器必须建议可用表的列表。但是，如果我返回到SELECT *，来自people，编辑器必须建议people表的字段列表。
如果我输入了以下内容：SELECT p.name，来自people p左连接地址a ON p.address_id = a.id的.\x{e76f}，编辑器必须建议地址表的字段列表。
另外，如何支持子查询？
浏览 3提问于2014-09-24得票数 0
1回答
从后缀树生成后缀
、、
我已经在网站的基础上用Java语言构建了一个后缀树，但我遇到了一个问题。我可以很好地构建一个后缀树，但我可以尝试从树中构建一组所有后缀。我基本上找到了所有的'end node‘并返回由那个'end node’表示的字符串
这个算法适用于像“记账员”这样的单词。
├── (1) bookkeeper
├── (9) e
│ ├── (8) eper
│ ├── (10) per
│ └── (12) r
├── (6) k
│ ├── (7) eeper
│ └── (5) keeper
├── (3) o
│ ├── (4) kkeeper
│ └─
浏览 0提问于2012-04-09得票数 1
回答已采纳
2回答
字符串处理
、、
一个字符串'hello'，如何列出所有单词和每个单词的计数。正常的后缀树算法只返回后缀，这意味着中间的单词'll‘不会出现。有人能帮我一步一步地解决吗？
浏览 3提问于2011-09-20得票数 0
回答已采纳
1回答
我逐渐了解到后缀树对于许多与字符串相关的任务来说是非常优秀和有用的结构，我想了解更多关于后缀树的知识。有人能建议一个好的起点来理解这些东西吗？也就是说，我不需要一些现成的代码或库来实现它，但可能需要一些教程来展示它们是如何构建的，以及您可以用它们做些什么。我喜欢“娱乐编程”，后缀树在我的学习列表中名列前茅:)
PS:我更喜欢Delphi/pascal，但是欢迎任何语言的教程。
浏览 0提问于2011-10-18得票数 0
回答已采纳
1回答
如何使用trie在两个或多个字符串中找到LCS (最长公用子字符串)？
我有一个这样的想法-假设我的第一个字符串是"abbcabdd“。然后我将首先在trie中插入"abbcabdd“，然后是"bbcabdd"，然后是"bcabdd”....，然后是"d“，并对每个字符串重复此过程。
然后通过遍历trie来计算最长的子串。
但我认为它的效率并不高。还有没有其他改进的方法？
浏览 0提问于2012-10-17得票数 1
2回答
我通过互联网读到了一些信息.我发现后缀树与后缀数组很相似，但不知怎么的，它们不是一回事。
给定一个字符串，后缀树构造算法如下所示(我从一个网站复制了该算法)。
FOR i ← 1 to n-1
FOR j ← 1 to i+1
find the end path for S[j…i]
extend the path, if needed, to S[i+1]
后缀树，可以列出从给定字符串中获得的所有减法。
但是，后缀数组是否也提供了相同的功能来获得子字符串列表？还是后缀数组只是后缀树的实现？还是后缀数组只是提供了一些存储功能？
浏览 0提问于2011-09-15得票数 3
1回答
找出一组等长字符串的重叠部分？
、、、、
有一百万个等长字符串(短串).For示例
abcdefghi
fghixyzyz
ghiabcabc电缆
zyzdddxfg
。。。
我想找出A"abcdefghi“和B"fghixyzyz”的两个string.The重叠的成对重叠是"fghi"，这是A的最大后缀，B的最大前缀，满足后缀和前缀相等。
是否有有效的算法可以找到集合中任意两个字符串的重叠？
浏览 5提问于2012-05-25得票数 3
2回答
我的代码工作，我正在寻找更聪明的想法，以提高效率？
对于字符串相似性，它被定义为最长的公共前缀长度，例如，"abc“和"abd”为2，"aaa“和"aaab”为3。
问题是计算字符串S及其所有后缀的相似性，包括作为第一个后缀的本身。
例如，对于S="ababaa"，后缀是“ababaa”、"babaa“、"abaa”、"baa“、"aa”和"a"，相似的是6+0+3+0+1+1=11。
# Complete the function below.
from collections import de
浏览 6提问于2016-02-16得票数 0
回答已采纳
我正面临着一个应该使用Aho-Corasick自动机来解决的问题。我得到了一组单词(由'0‘或’1‘组成)-模式，我必须决定是否可以创建无限的文本，其中不包含任何给定的模式。我认为，解决方案是创建Aho-Corasick自动机并搜索没有匹配状态的循环，但我不能提出一个好的方法来做到这一点。我想过使用DFS搜索状态图，但我不确定它是否可以工作，并且我有一个实现问题--让我们假设我们在一个状态中，它有一个'1‘边-但是那个边指向的状态被标记为匹配-所以我们不能使用那个边，我们可以尝试失败链接(当前状态没有'0’边)-但我们也必须记住，我们不能使用当前状态的失败链接指向的状态
浏览 2提问于2013-03-04得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
