标签: levenshtein-distance

我正在使用levenshtein算法来满足这些要求:

当找到N个字符的单词时,在我的字典数据库中建议更正的单词是:

N个字符的每个字典单词,与找到的单词有1个字符差异.示例:找到单词:bearn,dictionary word:bears

N + 1个字符的每个字典单词,其N个字符等于找到的单词.示例:找到的单词:bear,dictionary word:bears

N-1个字符的每个字典单词,其N-1个字符等于找到的单词.示例:找到单词:bears,dictionary word:bear

我在C++中使用Levenshtein算法的这种实现来找到一个单词的Levenshtein数为1(这是所有三种情况下的Levenshtein数),但是我如何选择这个单词来建议呢？我读到了Boyer-Moore-Horspool和Knuth-Morris-Pratt,但我不确定他们中的任何一个是如何有用的.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int levenshtein(const string &s1, const string &s2)
{
   string::size_type N1 = s1.length();
   string::size_type N2 = s2.length();
   string::size_type i, j;
   vector<int> T(N2+1);

   for ( i = 0; i <= N2; i++ )
      T[i] = i;

   for ( i = 0; i < N1; i++ ) {
      T[0] = i+1;
      int corner = i;
      for ( j = 0; j < N2; …

我有一个Postgres后端的Rails应用程序.

我需要添加全文搜索,这将允许基于Levenshtein距离或其他类似指标的模糊搜索.添加词法分析器/词干分析器必须使用非英语单词这一事实(可以在lexing时关闭与语言相关的功能,而不是弄乱目标语言,这可能会使英语引擎认为有意义的单词无关紧要).

我想Postgres的研究不会在这里适用,因为它没有模糊搜索 - 如果我错了,请纠正我.

后端和插件的可能组合有哪些？它更喜欢在基础设施上添加较少的解决方案(例如,如果Postgres可以有模糊fts,为什么要使用外部Lucene); OTOH,Rails插件的质量也很重要.

你会推荐什么？

更新:似乎我需要比Levenshtein更基于n-gram的指标.

我有一个很长的单词列表,我把它放入一个非常简单的SOLR/Lucene数据库.我的目标是从列表中为单项查询找到"相似"的单词,其中"相似性"特别理解为(damerau)levensthein编辑距离.我知道SOLR为拼写建议提供了这样的距离.

在我的SOLR中schema.xml,我配置了一个字段类型string:

<fieldType name="string" class="solr.StrField" sortMissingLast="true" omitNorms="true"/>

我用它来定义一个字段

<field name='term' type='string' indexed='true' stored='true' required='true'/>

我想搜索这个字段,并根据他们的levenshtein编辑距离返回结果.但是,当我webspace~0.1通过调试和解释运行类似于SOLR 的查询时,报告显示计算得分时需要考虑大量因素,例如:

"1582":"
1.1353534 = (MATCH) sum of:
  1.1353534 = (MATCH) weight(term:webpage^0.8148148 in 1581), product of:
    0.08618848 = queryWeight(term:webpage^0.8148148), product of:
      0.8148148 = boost
      13.172914 = idf(docFreq=1, maxDocs=386954)
      0.008029869 = queryNorm
    13.172914 = (MATCH) fieldWeight(term:webpage in 1581), product of:
      1.0 = tf(termFreq(term:webpage)=1)
      13.172914 = idf(docFreq=1, maxDocs=386954)
      1.0 = fieldNorm(field=term, doc=1581)

很明显,对于我的应用,术语频率,idfs等是没有意义的,因为每个文档只包含一个术语.我试图使用拼写建议组件,但没有设法让它返回实际的相似性分数.

有谁能够提供线索如何配置SOLR与返回分数和执行levensthein /哈罗-温克勒/ n元搜索没有做额外的东西一样tf, …

我已经阅读了关于计算两个不同单词之间距离的Levenshtein距离.

我有一个源字符串,我必须将它与所有10,000个目标字匹配.应该返回最接近的单词.

问题是我给出了10,000个目标词的列表,输入源词也很大....所以在这里应用什么最短,最有效的算法.每个组合(蛮力逻辑)的每个n的Levenshtein距离计算将非常耗时.

任何提示或想法都是最受欢迎的.

所以,我从这开始:http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Ruby

这适用于非常小的字符串.但是,我的字符串长度超过10,000个字符 - 由于Levenshtein距离是递归的,这会导致我的Ruby on Rails应用程序中出现堆栈太深的错误.

那么,是否有另一种可能更少的堆栈密集方法来找到两个大字符串之间的相似性？

或者,我需要一种方法来使堆栈具有更大的尺寸.(我不认为这是解决问题的正确方法)

我想使用Lucene来索引/搜索文本.文本可能包含错误的单词,名称等.让Lucene找到包含文档的最简单方法是什么

"this is Licene" 

当用户搜索时

"Lucene"? 

这仅适用于演示应用,因此我们需要最简单的解决方案.

我正在寻找Javascript中的通用Levenshtein实现。它必须快速并且对短字符串和长字符串有用。它也应该多次使用（因此进行缓存）。最重要的是，它计算出一个简单的Levenshtein距离。我想出了这个：

var levenshtein = (function() {
    var row2 = [];
    return function(s1, s2) {
        if (s1 === s2) {
            return 0;
        } else {
            var s1_len = s1.length, s2_len = s2.length;
            if (s1_len && s2_len) {
                var i1 = 0, i2 = 0, a, b, c, c2, row = row2;
                while (i1 < s1_len)
                    row[i1] = ++i1;
                while (i2 < s2_len) {
                    c2 = s2.charCodeAt(i2);
                    a = i2;
                    ++i2;
                    b = i2;
                    for (i1 = 0; i1 < s1_len; ++i1) …

我一直在阅读和测试php levenshtein中的一些例子.将$ input与$ words输出进行比较比较

$input = 'hw r u my dear angel';

    // array of words to check against
    $words  = array('apple','pineapple','banana','orange','how are you',
                    'radish','carrot','pea','bean','potato','hw are you');

输出

Input word: hw r u my dear angel
Did you mean: hw are you?

比较,删除hw你在阵列中.

$input = 'hw r u my dear angel';

    // array of words to check against
    $words  = array('apple','pineapple','banana','orange','how are you',
                    'radish','carrot','pea','bean','potato');

在第二个删除hw你是在数组输出

Input word: hw r u my dear angel
Did you …

我正在为我的学校制作一个系统,我们可以检查学生是否入围黑人,参加派对和其他活动.我很容易检查学生是否被列入黑名单,因为我可以在我的数据库中查看学生并查看他/她是否列入黑名单.

这是困难的地方.

在我们的聚会上,每个学生都可以邀请一个人.理论上,黑名单的学生可以被另一名学生邀请并绕过该系统.我无法查看黑名单上的学生的客人表,因为当您邀请客人时只提供姓名.

因此,我需要检查列入黑名单的名称是否接近访客姓名,如果它们已经关闭则显示警告,遗憾的是有些内容需要考虑.

名字可能完全不同.在丹麦,标准名称包含三个"名字",如"Niels Faurskov Andersen"但学生可能只需键入"Niels Faurskov"或"Niels Andersen",甚至可以删除一些字符.

所以像Niels Faurskov Andersen这样的全名可能是

• 尼尔斯安徒生
• Niels Faurskov
• Niels Faurskov Andersen
• Nils Faurskov Andersen
• 尼尔斯安徒生
• 尼尔斯福斯科夫
• 尼尔斯福斯科夫

等等...

另一件事是丹麦字母除了通常的az之外还包含"æøå".据说,整个站点和数据库都是UTF-8编码的.

我已经研究了各种方法来检查两个字符串之间的区别,而Levenshtein距离并没有完全发挥作用.

我在StackOverflow上找到了这个线程:获得最接近的字符串匹配

这似乎提供了正确的数据,但我不太确定选择哪种方法

我在php编写这部分代码,是否有人知道如何做到这一点？也许与MySQL？或Levenshtein距离的修改版本？正则表达式可以吗？

这是我要尝试做的事情：我想使用bash测量两根琴弦之间的Levensthein距离。我在这里找到了LD的实现。

现在，假设我有一些玩具数据，例如：

1    The brown fox jumped    The green fox jumped
0    The red fox jumped    The green fox jumped
1    The gray fox jumped    The green fox jumped

并说它存储在中data.test。

然后，我通过一个简单的awk命令将其过滤掉，1以此类推：

awk -F '\t' '{if ($1>0) print $2,t,$3}' data.test

然后，此简单命令的第一个输出将是：

The brown fox jumped    The green fox jumped

现在，我想通过将输出直接管道传递到此函数（从以上链接中提取）来测量这两个句子之间的Levensthein距离：

function levenshtein {
    if (( $# != 2 )); then
        echo "Usage: $0 word1 word2" >&2
    elif (( ${#1} < ${#2} …