当前位置:首页 > 开发 > 数据库 > 正文

最佳字符串匹配算法(Damerau-Levenshtein距离算法)的Java实现

发表于: 2013-11-11   作者:datamachine   来源:转载   浏览:
摘要: 原文:http://www.javacodegeeks.com/2013/11/java-implementation-of-optimal-string-alignment.html------------------------------------------------------------------------------------------------------------

原文:http://www.javacodegeeks.com/2013/11/java-implementation-of-optimal-string-alignment.html
---------------------------------------------------------------------------------------------------------------------------------

For a while, I’ve used the Apache Commons lang StringUtils implementation ofLevenshtein distance.  It implements a few well known tricks to use less memory by only hanging on to two arrays instead of allocating a huge n x m table for the memoisation table.  It also only checks a “stripe” of width 2 * k +1 where k is the maximum number of edits.

 

In most practical usages of levenshtein you just care if a string is within some small number (1, 2, 3) of edits from another string.  This avoid much of the n * m computation that makes levenstein “expensive”.  We found that with a k <= 3, levenshtein with these tricks was faster than Jaro-Winkler distance, which is an approximate edit distance calculation that was created to be a faster approximate (well there were many reasons).

 

Unfortunately, the Apache Commons Lang implementation only calculates Levenshtein and not the possible more useful Damerau-Levenshtein distance.  Levenshtein defines the edit operations insert, delete, and substitute.  The Damerau variant adds *transposition* to the list, which is pretty useful for most of the places I use edit distance.  Unfortunately DL distance is not a true metric in that it doesn’t respect the triangle inequality, but there are plenty of applications that are unaffected by this.  As you can see from that wikipedia page, there is often confusion between Optimal String Alignment and DL distance.  In practice OSA is a simpler algorithm and requires less book-keeping so the runtime is probably marginally faster.

 

I could not find any implementations of OSA or DL that used the memory tricks and “stripe” tricks that I saw in Apache Commons Lang.  So I implemented my own OSA using those tricks.  At some point I’ll also implement DL with the tricks and see what the performance differences are:

 

Here’s OSA in Java.  It’s public domain; feel free to use as you like. The unit tests are below. Only dependency is on Guava- but its just the preconditions class and an annotation for documentation so easy to remove that dependency if you like:

 

package com.github.steveash.util;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.primitives.Shorts.checkedCast;
import static java.lang.Math.abs;
import static java.lang.Math.max;

import java.util.Arrays;

import com.google.common.annotations.VisibleForTesting;

/**
 * Implementation of the OSA which is similar to the Damerau-Levenshtein in that it allows for transpositions to
 * count as a single edit distance, but is not a true metric and can over-estimate the cost because it disallows
 * substrings to edited more than once.  See wikipedia for more discussion on OSA vs DL
 * <p/>
 * See Algorithms on Strings, Trees and Sequences by Dan Gusfield for more information.
 * <p/>
 * This also has a set of local buffer implementations to avoid allocating new buffers each time, which might be
 * a premature optimization
 * <p/>
 * @author Steve Ash
 */
public class OptimalStringAlignment {

    private static final int threadLocalBufferSize = 64;

    private static final ThreadLocal<short[]> costLocal = new ThreadLocal<short[]>() {
        @Override
        protected short[] initialValue() {
            return new short[threadLocalBufferSize];
        }
    };

    private static final ThreadLocal<short[]> back1Local = new ThreadLocal<short[]>() {
        @Override
        protected short[] initialValue() {
            return new short[threadLocalBufferSize];
        }
    };

    private static final ThreadLocal<short[]> back2Local = new ThreadLocal<short[]>() {
        @Override
        protected short[] initialValue() {
            return new short[threadLocalBufferSize];
        }
    };

    public static int editDistance(CharSequence s, CharSequence t, int threshold) {
        checkNotNull(s, "cannot measure null strings");
        checkNotNull(t, "cannot measure null strings");
        checkArgument(threshold >= 0, "Threshold must not be negative");
        checkArgument(s.length() < Short.MAX_VALUE, "Cannot take edit distance of strings longer than 32k chars");
        checkArgument(t.length() < Short.MAX_VALUE, "Cannot take edit distance of strings longer than 32k chars");

        if (s.length() + 1 > threadLocalBufferSize || t.length() + 1 > threadLocalBufferSize)
            return editDistanceWithNewBuffers(s, t, checkedCast(threshold));

        short[] cost = costLocal.get();
        short[] back1 = back1Local.get();
        short[] back2 = back2Local.get();
        return editDistanceWithBuffers(s, t, checkedCast(threshold), back2, back1, cost);
    }

    @VisibleForTesting
    static int editDistanceWithNewBuffers(CharSequence s, CharSequence t, short threshold) {
        int slen = s.length();
        short[] back1 = new short[slen + 1];    // "up 1" row in table
        short[] back2 = new short[slen + 1];    // "up 2" row in table
        short[] cost = new short[slen + 1];     // "current cost"

        return editDistanceWithBuffers(s, t, threshold, back2, back1, cost);
    }

    private static int editDistanceWithBuffers(CharSequence s, CharSequence t, short threshold,
            short[] back2, short[] back1, short[] cost) {

        short slen = (short) s.length();
        short tlen = (short) t.length();

        // if one string is empty, the edit distance is necessarily the length of the other
        if (slen == 0) {
            return tlen <= threshold ? tlen : -1;
        } else if (tlen == 0) {
            return slen <= threshold ? slen : -1;
        }

        // if lengths are different > k, then can't be within edit distance
        if (abs(slen - tlen) > threshold)
            return -1;

        if (slen > tlen) {
            // swap the two strings to consume less memory
            CharSequence tmp = s;
            s = t;
            t = tmp;
            slen = tlen;
            tlen = (short) t.length();
        }

        initMemoiseTables(threshold, back2, back1, cost, slen);

        for (short j = 1; j <= tlen; j++) {
            cost[0] = j; // j is the cost of inserting this many characters

            // stripe bounds
            int min = max(1, j - threshold);
            int max = min(slen, (short) (j + threshold));

            // at this iteration the left most entry is "too much" so reset it
            if (min > 1) {
                cost[min - 1] = Short.MAX_VALUE;
            }

            iterateOverStripe(s, t, j, cost, back1, back2, min, max);

            // swap our cost arrays to move on to the next "row"
            short[] tempCost = back2;
            back2 = back1;
            back1 = cost;
            cost = tempCost;
        }

        // after exit, the current cost is in back1
        // if back1[slen] > k then we exceeded, so return -1
        if (back1[slen] > threshold) {
            return -1;
        }
        return back1[slen];
    }

    private static void iterateOverStripe(CharSequence s, CharSequence t, short j,
            short[] cost, short[] back1, short[] back2, int min, int max) {

        // iterates over the stripe
        for (int i = min; i <= max; i++) {

            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                cost[i] = back1[i - 1];
            } else {
                cost[i] = (short) (1 + min(cost[i - 1], back1[i], back1[i - 1]));
            }
            if (i >= 2 && j >= 2) {
                // possible transposition to check for
                if ((s.charAt(i - 2) == t.charAt(j - 1)) &&
                        s.charAt(i - 1) == t.charAt(j - 2)) {
                    cost[i] = min(cost[i], (short) (back2[i - 2] + 1));
                }
            }
        }
    }

    private static void initMemoiseTables(short threshold, short[] back2, short[] back1, short[] cost, short slen) {
        // initial "starting" values for inserting all the letters
        short boundary = (short) (min(slen, threshold) + 1);
        for (short i = 0; i < boundary; i++) {
            back1[i] = i;
            back2[i] = i;
        }
        // need to make sure that we don't read a default value when looking "up"
        Arrays.fill(back1, boundary, slen + 1, Short.MAX_VALUE);
        Arrays.fill(back2, boundary, slen + 1, Short.MAX_VALUE);
        Arrays.fill(cost, 0, slen + 1, Short.MAX_VALUE);
    }

    private static short min(short a, short b) {
        return (a <= b ? a : b);
    }

    private static short min(short a, short b, short c) {
        return min(a, min(b, c));
    }
}






 

最佳字符串匹配算法(Damerau-Levenshtein距离算法)的Java实现

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
0.序 相信大家对快捷键ctrl+F是做什么用的都应该很熟悉了,无论是文本编辑、网页浏览等程序上它都意
字符串面试题系列之七:字符串全排列 编译环境 本系列文章所提供的算法均在以下环境下编译通过。 【
处理字符串的过程中,难免会遇到字符匹配的问题。常用的字符匹配方法 1. 朴素模式匹配算法(Brute-Fo
上一篇文章,我介绍了 KMP算法。 但是,它并不是效率最高的算法,实际采用并不多。各种文本编辑器的
   字符串匹配是计算机的基本任务之一。   举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",
作者: 阮一峰 日期: 2013年5月 1日 字符串匹配是计算机的基本任务之一。 举例来说,有一个字符串"
1、BDM算法使用后缀自动机搜索子串。后缀自动机决定字符串U是否为模式串P的子串图示如下: 1)可以
1、BNDM算法与BDM相似,它维护一个集合,即位向量D=Dm....D1,用这个位向量的位记录u在P的反转串中的
字符串匹配 -- KMP算法 参考资料 1 数据结构( C 语言版) 2 Matrix67 : KMP算法详解 3 任我行 :KMP
当两个字符串进行顺序匹配出现某字符匹配不正确时,被匹配字串的开始位置要回退,这是个不效率的工
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号