相关疑难解决方法(0)

我正在寻找一种字符串相似度算法,它可以在变长字符串上产生比通常建议的更好的结果(levenshtein距离,soundex等).

例如,

鉴于字符串A:"罗伯特",

然后是字符串B:"Amy Robertson"

会比一个更好的比赛

字符串C:"理查德"

此外,优选地,该算法应该是语言不可知的(也可以用于除英语之外的语言).

如何查询按相似性排序的记录？

例如.搜索"股票溢出"将返回

1. 堆栈溢出
2. SharePoint溢出
3. 数学溢出
4. 政治溢出
5. VFX溢出

例如.搜索"LO"将返回:

1. 巴勃罗毕加索
2. 米开朗基罗
3. 杰克逊pollock

我需要帮助的是:

1. 使用搜索引擎索引和搜索MySQL表,以获得更好的结果

   • 使用Sphinx搜索引擎,使用PHP

   • 使用带有PHP 的Lucene引擎

2. 使用全文索引,查找类似/包含的字符串

什么不好用

• Levenshtein距离非常不稳定.(UDF,查询)
  搜索"狗"给了我:
  1. 狗
  2. 沼泽
  3. 前
  4. 大
  5. 回声
• LIKE 返回更好的结果,但对于长查询不返回任何内容,尽管存在类似的字符串
  1. 狗
  2. dogid
  3. dogaral
  4. 教条

在工作中,我们经常需要从与其他输入字符串最匹配的字符串列表中查找字符串.目前,我们正在使用Needleman-Wunsch算法.该算法通常会返回大量误报(如果我们将最小分数设置得太低),有时候它应该找不到匹配(当最小分数太高时),并且大多数时候,我们需要手工检查结果.我们认为我们应该尝试其他替代品.

您对算法有任何经验吗？你知道算法如何相互比较吗？

我真的很感激一些建议.

PS:我们用C#编码,但你不应该关心它 - 我一般都在询问算法.

哦,对不起,我忘记提及了.

不,我们不是用它来匹配重复数据.我们有一个我们正在寻找的字符串列表 - 我们称之为搜索列表.然后我们需要处理来自各种来源的文本(如RSS提要,网站,论坛等) - 我们提取这些文本的一部分(有完整的规则集,但这是无关紧要的)我们需要匹配那些反对搜索列表的人.如果字符串匹配search-list中的一个字符串 - 我们需要对事物进行一些进一步的处理(这也是无关紧要的).

我们无法执行正常的比较,因为从外部源提取的字符串,大多数时候,包括一些额外的单词等.

无论如何,它不是重复检测.

我有一个相当大的字符串集(比如100),它有许多以其相似性为特征的子组.我试图找到/设计一个算法,可以合理有效地找到这些组.

举个例子,假设输入列表位于左下方,输出组位于右侧.

Input                           Output
-----------------               -----------------
Jane Doe                        Mr Philip Roberts
Mr Philip Roberts               Phil Roberts     
Foo McBar                       Philip Roberts   
David Jones                     
Phil Roberts                    Foo McBar        
Davey Jones            =>         
John Smith                      David Jones      
Philip Roberts                  Dave Jones       
Dave Jones                      Davey Jones      
Jonny Smith                     
                                Jane Doe         

                                John Smith       
                                Jonny Smith 

有没有人知道如何合理有效地解决这个问题？

寻找类似字符串的标准方法似乎是Levenshtein距离,但我无法看到如何在这里充分利用它,而不必将每个字符串与列表中的每个其他字符串进行比较,然后以某种方式决定差异判断两个字符串是否在同一组中的阈值.

另一种方法是将字符串分解为整数的算法,其中类似的字符串散列为在数字行上靠近的整数.我不知道会是什么算法,如果有的话甚至存在

有没有人有任何想法/指示？

更新:@Will A:也许名字并不像我最初想的那么好.作为一个起点,我认为我可以假设在我将使用的数据中,字符串中的一个小变化不会使它从一个组跳到另一个组.

我正在寻找一种算法,或者至少是关于如何在两个或多个不同的字符串中找到类似文本的操作理论......

就像这里提出的问题一样:查找具有相似文本的文章的算法,区别在于我的文本字符串只会是少数单词.

就像说我有一个字符串:"进入清澈的蓝天",我正在与以下两个字符串进行比较:"颜色是天蓝色"和"在蓝色的晴空中"

我正在寻找一种可用于匹配两者中文本的算法,并决定它们的匹配程度.在我的情况下,拼写和标点符号将是重要的.我不希望它们影响发现真实文本的能力.在上面的例子中,如果颜色参考被存储为"'天蓝色'",我希望它仍然能够匹配.但是,列出的第3个字符串应该比第二个字符串更好,等等.

我敢肯定谷歌这样的地方可能会使用类似于"你是不是的意思:"的功能......

*编辑*
在与朋友交谈时,他与一位撰写有关此主题的论文的人合作.我想我可能会与阅读此内容的所有人分享,因为其中描述了一些非常好的方法和流程......

这是他的论文的链接,我希望它对阅读这个问题的人以及类似的字符串算法的主题有所帮助.

有没有一种方法来计算字符串的一般"相似性得分"？在某种程度上,我不是将两个字符串比较在一起,而是我为每个字符串得到一些数字/分数(哈希),以后可以告诉我两个字符串是或不相似.两个相似的字符串应该具有相似(接近)的分数/哈希值.

让我们将这些字符串和分数视为一个例子:

你好世界1000

你好,世界!1010

你好地球1125

Foo bar 3250

FooBarbar 3750

Foo Bar!3300

Foo世界!2350

你可以看到Hello world!和Hello世界是相似的,他们的分数彼此接近.

这样,通过从其他分数中减去给定的字符串分数然后对其绝对值进行排序,可以找到与给定字符串最相似的字符串.

我的最终目标是:会有流式日志消息(只有纯消息),我想找到这些消息的模式(某种正则表达式类型).但是只有当我可以使用类似的字符串时它才会启动.我再次关注我应该为每个字符串获得一些数字/分数(哈希)并且可以告诉我两个字符串是否相似

我有一个包含300万人记录的表,我希望使用q-gram(例如姓氏)进行模糊匹配.我已经创建了一个2-gram链接表,但是在这个数据卷上搜索性能不是很好(大约5分钟).

我基本上有两个问题:(1)你能否提出任何提高性能的方法来避免表格扫描(即必须计算搜索字符串和300万个姓氏之间的常见q-gram)(2)q-gram,如果A类似于B和C类似于B,它是否意味着C类似于A？

亲切的问候

彼得

我在CareerCup.com上经历了一些亚马逊的采访问题,我偶然发现了一个有趣的问题,我无法弄明白该怎么做.自从2天以来我一直在考虑这个问题.无论是我采取的方式,还是一个真正难以写的功能.

问题如下:

在C中编写一个函数,可以查找字符串是否是另一个字符串的子字符串.请注意,应忽略一个字符的不匹配.

A mismatch can be an extra character: ’dog’ matches ‘xxxdoogyyyy’  
A mismatch can be a missing character: ’dog’ matches ‘xxxdgyyyy’ 
A mismatch can be a different character: ’dog’ matches ‘xxxdigyyyy’

问题中没有提到返回值,所以我假设函数的签名可以是这样的:

char * MatchWithTolerance(const char * str, const char * substr);

如果与给定规则匹配,则将指针返回到字符串中匹配子字符串的开头.否则返回null.

奖金

如果有人也可以找出一种通用的方法来对n进行公差而不是1,那么那就太棒了.在这种情况下,签名将是:

char * MatchWithTolerance(const char * str, const char * substr, unsigned int tolerance = 1);

感谢所有想要尝试并分享他们成功解决方案的人.

我有很长的单词列表,我想显示以用户输入的文本开头的单词.当用户输入字符时,应用程序应更新显示给用户的列表.它应该像Android上的AutoCompleteTextView.我只是想知道存储单词的最佳数据结构,以便搜索速度非常快.

假设我有 9 行记录。每 3 行具有相同的值。例如：

Mike  
Mike  
Mike  
John  
John  
John  
Ryan  
Ryan  
Ryan

有没有办法可以搜索这些记录的相似性？例如拼写错误、附加字符、缺失字符等。例如，正确的版本是Mike，但列表中可能有记录Mke不正确（拼写错误）。我怎样才能找到它并用正确的替换它？

上面的例子显然是简化的。我实际上有大约 100 万行。现在为了实现元素的“分组”，我只是按字母顺序对它们进行排序。