标签: levenshtein-distance

$word = strtolower($_GET['term']); 

$lev = 0;

$q = mysql_query("SELECT `term` FROM `words`"); 
while($r = mysql_fetch_assoc($q)) 
{ 
    $r['term'] = strtolower($r['term']); 

    $lev = levenshtein($word, $r['term']);

    if($lev >= 0 && $lev < 5)
    {
        $word = $r['term'];
    }
}

如何将所有内容移动到一个查询中？不希望查询所有术语并在PHP中进行过滤.

我有以下工作Java代码,用于搜索单词列表中的单词,并且它完美地工作并且符合预期:

public class Levenshtein {
    private int[][] wordMartix;

    public Set similarExists(String searchWord) {

        int maxDistance = searchWord.length();
        int curDistance;
        int sumCurMax;
        String checkWord;

        // preventing double words on returning list
        Set<String> fuzzyWordList = new HashSet<>();

        for (Object wordList : Searcher.wordList) {
            checkWord = String.valueOf(wordList);
            curDistance = calculateDistance(searchWord, checkWord);
            sumCurMax = maxDistance + curDistance;
            if (sumCurMax == checkWord.length()) {
                fuzzyWordList.add(checkWord);
            }
        }
        return fuzzyWordList;
    }

    public int calculateDistance(String inputWord, String checkWord) {
        wordMartix = new int[inputWord.length() + 1][checkWord.length() + 1];

        for …

我得到了levenshtein距离的代码,用于mysql格式"http://kristiannissen.wordpress.com/2010/07/08/mysql-levenshtein/"但是,如何在mysql中添加该函数？我正在使用xampp,我需要它在php中搜索.

我试图使用Levenshtein距离算法将单个搜索项与可能匹配的字典进行匹配.该算法返回一个距离,表示为将搜索字符串转换为匹配字符串所需的操作数.我想在排名最高的"N"(比方说10)比赛的百分比列表中显示结果.

由于搜索字符串可以比单个字典字符串更长或更短,因此将距离表示为百分比的适当逻辑将定性地反映出查询字符串的每个结果与"百分比"的接近程度,100 %表示完全匹配.

我考虑了以下选项:

Q = query string
M = matched string
PM = Percentage Match
Option 1. PMi = (1 - Lev_distance(Q, Mi)/Strlen(Q)) * 100
Option 2. PMi = (1 - Lev_distance(Q, Mi)/max(Strlen(Q), strlen(Mi))) * 100

如果距离大于搜索字符串长度(匹配字符串为长),则选项1可能为负百分比.例如查询"ABC"与"ABC Corp."匹配 会导致负匹配百分比.

选项2似乎不会在一组Mi中给出一致的百分比,因为每个计算可能使用不同的分母,因此得到的百分比值不会被标准化.

只有我能想到的另一种方法是抛弃lev_distance与字符串长度的比较,而是将顶部"N"匹配的比较距离表示为反百分位数等级(100百分位等级).

有什么想法吗？有更好的方法吗？我必须遗漏一些东西,因为Levenshtein距离可能是最常见的模糊匹配算法,这一定是一个非常常见的问题.

我正在使用Levenshtein算法来找到两个字符串之间的相似性.这是我正在制作的计划中非常重要的一部分,因此它需要有效.问题是该算法没有找到类似的以下示例:

CONAIR
AIRCON

该算法将给出6的距离.因此,对于6个字母的单词(您查看具有最高字母数量的单词),差异为100%=>相似度为0%.

我需要找到一种方法来找到两个字符串之间的相似之处,同时还要考虑像我之前提到的那样的情况.

我可以使用更好的算法吗？或者你们推荐我什么？

编辑:我也研究了"Damerau-Levenshtein"算法,它增加了换位.问题是这个转置仅适用于相邻字符(而不适用于多个字符).

是否有包含Levenshtein距离计数功能的包,它是作为C或Fortran代码实现的？我有很多的字符串进行比较,并stringMatch从MiscPsycho对这个太慢了.

根据python-Levenshtein.ratio消息来源:

https://github.com/miohtama/python-Levenshtein/blob/master/Levenshtein.c#L722

它被计算为(lensum - ldist) / lensum.这适用于

distance('ab', 'a') = 1
ratio('ab', 'a') = 0.666666

但是,它似乎打破了

distance('ab', 'ac') = 1
ratio('ab', 'ac') = 0.5

我觉得我必须遗漏一些非常简单的事情......但为什么不0.75呢？

我刚刚实现了一个最佳匹配文件搜索算法,以找到与字典中字符串最接近的匹配.在分析我的代码之后,我发现绝大部分时间花在计算查询和可能结果之间的距离上.我目前正在使用2-D数组实现算法来计算Levenshtein距离,这使得实现成为O(n ^ 2)运算.我希望有人可以建议更快的方式做同样的事情.

这是我的实现:

public int calculate(String root, String query)
{
  int arr[][] = new int[root.length() + 2][query.length() + 2];

  for (int i = 2; i < root.length() + 2; i++)
  {
    arr[i][0] = (int) root.charAt(i - 2);
    arr[i][1] = (i - 1);
  }

  for (int i = 2; i < query.length() + 2; i++)
  {
    arr[0][i] = (int) query.charAt(i - 2);
    arr[1][i] = (i - 1);
  }

  for (int i = 2; i < root.length() + 2; i++)
  { …

我正在研究一个非常粗略的初稿算法,以确定2个字符串的相似程度.我也使用Levenshtein Distance来计算字符串之间的编辑距离.

我目前正在做的是基本上采用编辑总数并将其除以较大字符串的大小.如果该值低于某个阈值,当前随机设置为25%,则它们"足够相似".

然而,这完全是任意的,我不认为这是计算相似性的一种非常好的方法.是否有某种数学方程或概率/统计方法来获取Levenshtein距离数据并使用它来说"是的,根据所做的编辑数量和字符串的大小,这些字符串是否足够相似"？

此外,关键是我使用任意阈值,我宁愿不这样做.如何计算此阈值而不是分配它,以便我可以安全地说2个字符串"足够相似"？

UPDATE

我正在比较代表Java堆栈跟踪的字符串.我想这样做的原因是通过相似性对一堆给定的堆栈跟踪进行分组,并将其用作过滤器来对"东西"进行排序:)这种分组对于我无法公开分享的更高级别的原因很重要.

到目前为止,我的算法(伪代码)大致如下:

/*
 * The input lists represent the Strings I want to test for similarity. The
 * Strings are split apart based on new lines / carriage returns because Java
 * stack traces are not a giant one-line String, rather a multi-line String.
 * So each element in the input lists is a "line" from its stack trace.
 */
calculate similarity (List<String> list1, List<String> list2) {

    length1 = 0; …

我有一个独立的CSV数据加载过程,我用Java编码,必须使用一些模糊的字符串匹配.这绝对不是理想的,但我没有太多选择.我使用名字和姓氏进行匹配,并在运行开始时缓存所有可能性.找到匹配后,我需要该人在运行期间对多个位置.我使用guava Objects.hashCode()来创建名字和姓氏的哈希值.

缓存机制如下所示:

Map<Integer,PersonDO> personCache = Maps.newHashMap();
for(PersonDO p: dao.getPeople()) {
    personCache.put(Objects.hashCode(p.getFirstName(),p.getLastName()), p);
}

大部分时间我都会在名字+姓氏上点击,但是当它错过时我会使用Apache StringUtils.getLevenshteinDistance()来尝试匹配它.这就是匹配逻辑流程的方式:

    person = personCache.get(Objects.hashCode(firstNameFromCSV,lastNameFromCSV));
    if(person == null) {//fallback to fuzzy matching
        person = findClosetMatch(firstNameFromCSV+lastNameFromCSV);

    }

这是findClosetMatch()方法:

private PersonDO findClosetMatch(String name) {
    int min = 15;//initial value
    int testVal=0;
    PersonDO matchedPerson = null;
    for(PersonDO person: personCache.values()) {
        testVal = StringUtils.getLevenshteinDistance(name,person.getFirstName()+person.getLastName());
        if( testVal < min ) {
            min = testVal;
            matchedPerson = person;
        }
    }
    if(matchedPerson == null) {
        throw new Exception("Unable to …