标签: string-algorithm

假设我有这个text = I love apples, kiwis, oranges and bananas和searchString = kiwis and bananas和相似度算法说Jaccard索引.如何有效地找到text与其具有最高相似性的子串searchString.

基本上我试图找到与我拥有的关键字列表匹配的文本部分(文本有高错误,拼写错误,额外符号和空格).

你如何在长长的角色中找到正确的单词？

输入:

"The revised report onthesyntactictheoriesofsequentialcontrolandstate"

谷歌的输出:

"The revised report on syntactic theories sequential controlandstate"

(考虑到他们产生输出的时间足够接近)

您认为Google如何做到这一点？你会如何提高准确度？

我正在开发一种类似于IDE的东西,它可以处理数以万计的非常大(文本)文件,我正在调查这个主题的最新技术水平.

作为一个例子,Intellij的标准(非正则表达式)表达式的搜索算法非常直接.他们是如何做到这一点的？他们只是在内存中保留所有可搜索文件的某种后缀树吗？他们只是将文件内容的很大一部分保存在内存中,这样他们只需要几乎完全内存的标准KMP来避免任何磁盘IO吗？

谢谢

字符串算法上有很多帖子:

• 查找具有相似文本的文章的算法,
• 类似String算法,
• 高效的字符串匹配算法

但是,没有提到一般文献.

任何人都可以推荐一本能彻底探索各种字符串算法的书吗？特别感兴趣的主题是近似字符串匹配[像谷歌提供的纠正搜索字符串变体:)].

非常感谢您的建议.

我有一个大城市数据库,它是从许多不同来源编译而来的.我正试图找到一种方法,可以根据城市名称轻松发现重复项.天真的答案是使用levenshtein距离.然而,城市的问题在于它们通常具有前缀和后缀,这些前缀和后缀对于它们所在的国家而言是共同的.

例如:

Boulleville对阵Boscherville

这些几乎肯定是不同的城市.然而,因为它们都以"ville"结尾(并且都以"Bo"开头),所以它们具有相当小的Levenstein距离.

*我正在寻找一种字符串距离算法,该算法考虑到字符的位置,通过将单词中间的字母加权高于单词末尾的字母来最小化前缀和后缀的影响.*

我本可以自己写一些东西,但我觉得很难相信没有人发表过合适的算法.

在PHP中是否有Aho-Corasick的工作实现？维基百科文章中提到的PHP中有一个Aho-Corasick字符串匹配:

<?php

/* 

    This class performs a multiple pattern matching by using the Aho-Corasick algorythm, which scans text and matches all patterns "at once".

    This class can:
    - find if any of the patterns occours inside the text
    - find all occourrences of the patterns inside the text
    - substitute all occourrences of the patterns with a specified string (empty as well)

    Example of usage: 

    $words = array{ "ananas", "antani", "assassin" };
    $pm = …

关于SO的另一个问题是将一些语言中的工具用于散列字符串,以便在表格中快速查找.两个例子是.NET中的dictionary <>和Python中的{}存储结构.其他语言当然支持这种机制.C++有它的地图,LISP和大多数其他现代语言一样具有等价物.

在问题的答案中争论的是,字符串上的哈希算法可以在一个持续时间内进行,其中一个SO成员具有25年的编程经验,声称任何事物都可以在恒定时间内进行哈希处理.我个人的论点是,这不是真的,除非你的特定应用程序在字符串长度上设置边界.这意味着一些常数K将决定字符串的最大长度.

我熟悉使用散列函数进行操作的Rabin-Karp算法,但是这个算法没有规定要使用的特定散列函数,作者建议的那个是O(m),其中m是长度.哈希字符串.

我看到一些其他页面,例如这个(http://www.cse.yorku.ca/~oz/hash.html)显示了一些哈希算法,但似乎每个页面都在字符串的整个长度上迭代达到它的价值.

根据我对该主题的相对有限的阅读,似乎大多数字符串类型的关联数组实际上是使用散列函数创建的,该散列函数在引擎盖下运行某种树.这可以是AVL树或红/黑树,其指向键/值对中的值元素的位置.

即使使用这种树结构,如果我们要保持theta(log(n))的顺序,n是树中元素的数量,我们需要有一个恒定时间的哈希算法.否则,我们会对字符串进行迭代处理.尽管对于包含许多字符串的索引,theta(m)会被theta(log(n))黯然失色,但如果我们处于这样一个域中,我们搜索的文本将非常大,我们就不能忽略它.

我知道后缀树/数组和Aho-Corasick可以将搜索降低到theta(m)以获得更大的内存费用,但是我要问的是,如果存在任意长度的字符串的常量时间哈希方法,那么其他SO成员声称.

谢谢.

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

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

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

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

叶子上的数字是多少？

（这个问题与音乐无关，但我将音乐用作用例的示例。）

在音乐中，构建乐句的常用方法是将中间部分重复一次或多次的一系列音符。因此，该短语由介绍、循环部分和结尾组成。这是一个例子：

[ E E E F G A F F G A F F G A F C D ]

我们可以“看到”前奏是[EEE]，重复部分是[FGA F]，结尾是[CD]。所以拆分列表的方法是

[ [ E E E ] 3 [ F G A F ] [ C D ] ]

其中第一项是前奏，第二项是重复部分的重复次数，第三部分是尾声。

我需要一个算法来执行这样的拆分。

但是有一个警告是可能有多种方法来拆分列表。例如，上面的列表可以拆分为：

[ [ E E E F G A ] 2 [ F F G A ] [ F C D ] ]

但这是一个更糟糕的分裂，因为前奏和后奏更长。所以算法的标准是找到最大化循环部分长度和最小化前奏和后奏组合长度的分割。这意味着正确的拆分为

[ A C C C C C C C C C A ] …

如何在O(n)中找到字符串的最长回文前缀？

给定一组50k字符串,我需要找到所有对(s, t),这样s,t并且s + t都包含在这个集合中.

我试过的

,还有一个额外的约束:s.length() >= 4 && t.length() >= 4.这使得可以通过长度为4的前缀和单独的后缀对字符串进行分组.然后,对于每个composed长度至少为8的字符串,我查找s使用前四个字符composed的候选集和t使用其最后四个字符的候选集.这有效,但需要查看30M候选对(s, t)才能找到7k结果.

这个令人惊讶的大量候选人来自这样一个事实,即字符串是来自有限词汇表的(主要是德语)单词,而单词的开头和结尾通常是相同的.它仍然比尝试所有2.5G对要好得多,但比我希望的要糟糕得多.

我需要的

由于附加约束可能会被删除而且集合会增长,我正在寻找更好的算法.

"失踪"的问题

有人抱怨我不问问题.所以缺少的问号在下一句的末尾.如何更有效地完成这项工作,理想情况下不使用约束？

我的问题是能够计算c中字符串中单引号或双引号的数量。例子

        String            Single Quote Count        Double Quote Count
     'hello world'                2                      0
     'hell'o world'               3                      0

     "hello world"                0                      2
     "hello" world"               0                      3

用户输入字符串，我通过 gets() 函数获取，然后我需要这个计数器来进一步分析该字符串。

例如，当我必须计算字符串中的“|”时，会更容易

        String            | Count        
     hello | world           1            
     hello | wo|rld          2            

所以我的功能很简单：

 int getNumPipe(char* cmd){
  int  num = 0;
  int i;
     for(i=0;i<strlen(cmd);i++){
       if(cmd[i]=='|'){ //if(condition)
       num++;
      }
     }

 return num;
}

但现在我必须分析报价，我不知道该为 if(condition) 添加什么

          if(cmd[i]==''')??