时间戳

首页 > 解决方案 > 查找所有相似词对

algorithm - 查找所有相似词对

问题描述

我有大约 40000 个单词，想找到所有相似的词对。为了相似性，我使用了一个按单词长度缩放的Damerau-Levenshtein 距离。为简单起见，我不考虑重叠编辑（就像链接算法一样）。所有单词（其中大部分是德语、法语或英语）都被转换为小写，因为我们的数据中没有任何信息。我对距离计算做了两次修改

此外，字符串 ß的距离ss设置为 0.2。我们的数据表明，这种并发症是必要的。

为了找到所有相似的对，我的想法是只考虑通过一个常见的n-gram找到的对，但这对于短词（这是可以接受的）失败并且通常是由于上述修改。

我的下一个想法是提前中止距离计算，如果已知结果超过阈值（比如 4）。然而，由于许多词都有共同的前缀，这种中止来得太晚，不能成为一个很好的加速。在常见的后缀上反转单词会失败（不是那么糟糕）。

所有 20e6 对的整个计算需要大约 5 分钟，所以现在，可以执行一次并存储所有结果（只需要低于阈值的距离）。但我正在寻找更具前瞻性的东西。

是否可以快速计算出 Damerau-Levenshtein 距离的良好下限（理想情况下允许提前退出）？

是否可以通过上述修改？请注意，例如，“至少两个字符串大小的差异”不成立，因为第二次修改。

编码

public final class Levenshtein {
    private static final class CharDistance {
        private static int distance(char c0, char c1) {
            if (c0 == c1) return 0;
            if ((c0|c1) < 0x80) return SCALE;
            return c0<=c1 ? distanceInternal(c0, c1) : distanceInternal(c1, c0);
        }

        private static int distanceInternal(char c0, char c1) {
            assert c0 <= c1;
            final String key = c0 + " " + c1;
            {
                final Integer result = CACHE.get(key);
                if (result != null) return result.intValue();
            }
            final int result = distanceUncached(c0, c1);
            CACHE.put(key, Integer.valueOf(result));
            return result;
        }

        private static int distanceUncached(char c0, char c1) {
            final String norm0 = Normalizer.normalize("" + c0, Normalizer.Form.NFD).replaceAll("[^\\p{ASCII}]", "");
            final String norm1 = Normalizer.normalize("" + c1, Normalizer.Form.NFD).replaceAll("[^\\p{ASCII}]", "");
            if (norm0.equals(norm1)) return DIACRITICS;
            assert c0 <= c1;
            if (c0=='s' && c1=='ß') return DIACRITICS;
            return SCALE;
        }

        private static final Map<String, Integer> CACHE = new ConcurrentHashMap<>();
    }

    /**
     * Return the scaled distance between {@code s0} and {@code s1}, if it's below {@code limit}.
     * Otherwise, return some lower bound ({@code >= limit}.
     */
    int distance(String s0, String s1, int limit) {
        final int len0 = s0.length();
        final int len1 = s1.length();
        int result = SCALE * (len0 + len1);
        final int[] array = new int[len0 * len1];
        for (int i0=0; i0<len0; ++i0) {
            final char c0 = s0.charAt(i0);
            for (int i1=0; i1<len1; ++i1) {
                final char c1 = s1.charAt(i1);
                final int d = CharDistance.distance(c0, c1);

                // Append c0 and c1 respectively.
                result = get(len0, array, i0-1, i1-1) + d;

                // Append c0.
                result = Math.min(result, get(len0, array, i0-1, i1) + SCALE);

                // Append c1.
                result = Math.min(result, get(len0, array, i0, i1-1) + SCALE);

                // Handle the "ß" <-> "ss" substitution.
                if (c0=='ß' && c1=='s' && i1>0 && s1.charAt(i1-1)=='s') result = Math.min(result, get(len0, array, i0-1, i1-2) + DIACRITICS);
                if (c1=='ß' && c0=='s' && i0>0 && s0.charAt(i0-1)=='s') result = Math.min(result, get(len0, array, i0-2, i1-1) + DIACRITICS);

                // Handle a transposition.
                if (i0>0 && i1>0 && s0.charAt(i0-1)==c1 && s1.charAt(i1-1)==c0) result = Math.min(result, get(len0, array, i0-2, i1-2) + SCALE);

                set(len0, array, i0, i1, result);
            }
            // Early exit.
            {
                final int j = i0 - len0 + len1;
                final int lowerBound = get(len0, array, i0, j);
                if (lowerBound >= limit) return lowerBound;
            }
        }
        return result;
    }

    // Simulate reading from a 2D array at indexes i0 and i1;
    private int get(int stride, int[] array, int i0, int i1) {
        if (i0<0 || i1<0) return SCALE * (i0+i1+2);
        return array[i1*stride + i0];
    }

    // Simulate writing to a 2D array at indexes i0 and i1;
    private void set(int stride, int[] array, int i0, int i1, int value) {
        array[i1*stride + i0] = value;
    }

    private static final int SCALE = 10;
    private static final int DIACRITICS = 2;
}

例句

rotwein
rotweincuv
rotweincuvee
rotweincuveé
rotweincuvée
rotweincuvúe
rotweindekanter
rotweinessig
rotweinfass
rotweinglas
rotweinkelch
rotweißkomposition
rotwild
roug
rouge
rougeaoc
rougeaop
rougeots
rougers
rouges
rougeáaop
rough
roughstock
rouladen
roulette
roumier
roumieu
round
rounded
roundhouse
rounds
rouret
rouss
roussanne
rousseau
roussi
roussillion
roussillon
route
rouvinez
rove
roveglia
rovere
roveri
rovertondo
rovo
rowan
rowein
roxburgh
roxx
roy
roya
royal
royalbl
royalblau
royaldanishnavy
royale
royales
royaline
royals
royer
royere
roze
rozenberg
rozes
rozier
rozès
rozés
roßberg
roßdorfer
roßerer
rpa
rr
rrvb
rry
rs
rsaftschorle
rsbaron
rscastillo
rsgut
rsl
rstenapfel
rstenberg
rstenbrõu
rt
rtd
rtebecker
rtebeker
ru
ruadh
ruanda
rub
rubaiyat
ruban
rubata
rubblez
rubenkov
rubeno
rubentino
ruber

标签： algorithmlevenshtein-distancedamerau-levenshtein

解决方案

我建议将所有单词放入trie中，然后递归地搜索 trie 自身。

生成 trie 应该很快，现在公共前缀相互匹配只计算一次，无论有多少单词共享它们。

当你在树中徘徊时，你确实必须跟踪很多状态，因为你的状态是，“所有我们可能处于计算中间的东西”。

推荐阅读