Apache Commons Lang 3.4 имеет такую реализацию:
<code>/**
* <p>Find the Levenshtein distance between two Strings if it's less than or equal to a given
* threshold.</p>
*
* <p>This is the number of changes needed to change one String into
* another, where each change is a single character modification (deletion,
* insertion or substitution).</p>
*
* <p>This implementation follows from Algorithms on Strings, Trees and Sequences by Dan Gusfield
* and Chas Emerick's implementation of the Levenshtein distance algorithm from
* <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a></p>
*
* <pre>
* StringUtils.getLevenshteinDistance(null, *, *) = IllegalArgumentException
* StringUtils.getLevenshteinDistance(*, null, *) = IllegalArgumentException
* StringUtils.getLevenshteinDistance(*, *, -1) = IllegalArgumentException
* StringUtils.getLevenshteinDistance("","", 0) = 0
* StringUtils.getLevenshteinDistance("aaapppp", "", 8) = 7
* StringUtils.getLevenshteinDistance("aaapppp", "", 7) = 7
* StringUtils.getLevenshteinDistance("aaapppp", "", 6)) = -1
* StringUtils.getLevenshteinDistance("elephant", "hippo", 7) = 7
* StringUtils.getLevenshteinDistance("elephant", "hippo", 6) = -1
* StringUtils.getLevenshteinDistance("hippo", "elephant", 7) = 7
* StringUtils.getLevenshteinDistance("hippo", "elephant", 6) = -1
* * * @param s первая строка, не должна быть нулевой * @param t вторая строка, не должна быть нулевой * @param threshold целевой порог,не должно быть отрицательным * @return результатом расстояния или {@code -1}, если расстояние будет больше порога * @throws IllegalArgumentException, если либо String input {@code null}, либо отрицательный порог * / public static int getLevenshteinDistance (CharSequences, CharSequence t, конечный порог int) {if (s == null || t == null) {throw new IllegalArgumentException ("Строки не должны быть нулевыми");} if (threshold <0) {throw new IllegalArgumentException («Порог не должен быть отрицательным»);} / * Эта реализация вычисляет расстояние, только если оно меньше или равно пороговому значению, и возвращает -1, если оно больше.Преимущество - производительность: неограниченное расстояние равно O (нм), но ограничение k позволяет сократить его до времени O (км), вычисляя только диагональную полосу шириной 2k + 1 таблицы затрат.Это также можно использовать для вычисления неограниченного расстояния Левенштейна, начиная порог с 1 и удваивая каждый раз, пока расстояние не будет найдено;это O (dm), где d - расстояние.Одна тонкость возникает из-за необходимости игнорировать записи на границе нашей полосы, например.p [] = | # | # | # | * d [] = * | # | # | # |Мы должны игнорировать запись слева от крайнего левого элемента. Мы должны игнорировать запись над крайним правым элементом. Еще одна тонкость заключается в том, что наша полоса убегает из матрицы, если строки имеют разный размер.Поскольку строка s всегда поменяется местами, чтобы быть короче из двух, полоса всегда будет уходить в верхний правый угол вместо нижнего левого угла матрицы.В качестве конкретного примера, предположим, что s имеет длину 5, t имеет длину 7, и наш порог равен 1. В этом случае мы собираемся пройти полосу длины 3. Матрица будет выглядеть так: 1 2 3 45 1 | # | # ||||2 | # | # | # |||3 || # | # | # ||4 ||| # | # | # |5 |||| # | # |6 ||||| # |7 ||||||Обратите внимание на то, как полоса уходит со стола, так как нет возможности превратить строку длины 5 в строку длины 7 на расстоянии редактирования 1. Кроме того, эта реализация уменьшает использование памяти, используя два одномерных массива и меняя их обратно.и далее вместо того, чтобы выделять всю матрицу n на m.Это требует нескольких незначительных изменений, таких как немедленный возврат, когда обнаружено, что полоса вышла за пределы матрицы, и начальное заполнение массивов большими значениями, так что записи, которые мы не вычисляем, игнорируются.Посмотрите Алгоритмы на Струнах, Деревьях и Последовательностях Дэном Гасфилдом для некоторого обсуждения.* / int n = s.length ();// длина s int m = t.length ();// длина t // если одна строка пуста, расстояние редактирования обязательно равно длине другой if (n == 0) {return m <= threshold?м: -1;} иначе если (m == 0) {вернуть n <= порог?n: -1;} if (n> m) {// меняем две строки, чтобы использовать меньше памяти final CharSequence tmp = s;s = t;t = tmp;n = m;m = t.length ();} int p [] = new int [n + 1];// «предыдущий» массив затрат, по горизонтали int d [] = new int [n + 1];// массив затрат, горизонтально int _d [];// заполнитель для помощи в замене p и d // заполнение начальных значений таблицы final int border = Math.min (n, threshold) + 1;for (int i = 0; i Integer.MAX_VALUE - порог)?n: Math.min (n, j + порог);// полоса может выводить из таблицы, если s и t имеют разные размеры if (min> max) {return -1;} // игнорируем запись слева от самого левого, если (min> 1) {d [min - 1] = Integer.MAX_VALUE;} // перебирает [min, max] в s для (int i = min; i <= max; i ++) {if (s.charAt (i - 1) == t_j) {// по диагонали влево и вверх d [i] = p [i - 1];} else {// 1 + минимум ячейки слева, сверху, по диагонали влево и вверх d [i] = 1 + Math.min (Math.min (d [i - 1], p [i]),p [i - 1]);}} // копируем текущий счетчик расстояний в «предыдущий ряд» счетчик расстояний _d = p;р = д;d = _d;} // если p [n] больше порогового значения, нет гарантии, что оно будет правильным // расстоянием if (p [n] <= threshold) {return p [n];} возврат -1;} </code>