Расстояние редактирования слова на уровне слова

Ответ 1

Вы можете использовать те же алгоритмы, которые используются для поиска расстояния редактирования в строках, чтобы найти расстояния редактирования в предложениях. Вы можете придумать предложение как строку, взятую из алфавита, где каждый символ является словом на английском языке (предполагая, что пробелы используются для обозначения того, где начинается один "символ", а следующий заканчивается). Любой стандартный алгоритм вычисления расстояния редактирования, например стандартный подход динамического программирования для вычисления расстояния Левенштейна, может быть адаптирован для решения этой проблемы.

Ответ 2

В общем, это называется проблема выравнивания последовательностей. На самом деле неважно, какие объекты вы выровняете - биты, символы, слова или базы ДНК - пока алгоритм работает для одного типа элементов, он будет работать на все остальное. Важно то, хотите ли вы глобальное или локальное выравнивание.

Глобальное выравнивание, которое пытается выровнять каждый остаток в каждой последовательности, наиболее полезно, когда последовательности похожи и имеют примерно одинаковый размер. Общим методом глобального выравнивания является алгоритм алгоритм Needleman-Wunsch, который основан на динамическое программирование. Когда люди говорят о расстоянии Левинштейна, они обычно означают глобальное выравнивание. Алгоритм настолько прост, что несколько человек открыли его самостоятельно, и иногда вы можете встретить алгоритм Вагнера-Фишера, который по сути является тем же, но чаще упоминается в контексте расстояния редактирования между двумя строками символов.

Локальное выравнивание более полезно для разнородных последовательностей, которые, как предполагается, содержат области сходства или похожие мотивы последовательности в их более широком контексте контекста. алгоритм Smith-Waterman - это общий метод локального выравнивания, основанный также на динамическом программировании. Он довольно редко используется в обработке на естественном языке, а чаще - в биоинформатике.

Ответ 3

Вот пример реализации идеи @templatetypedef в ActionScript (она отлично работала для меня), которая вычисляет нормированное расстояние Левенштейна (или, другими словами, дает значение в диапазоне [0..1])

  private function nlevenshtein(s1:String, s2:String):Number {
     var tokens1:Array = s1.split(" ");
     var tokens2:Array = s2.split(" ");
     const len1:uint = tokens1.length, len2:uint = tokens2.length;
     var d:Vector.<Vector.<uint> >=new Vector.<Vector.<uint> >(len1+1);
     for(i=0; i<=len1; ++i)
        d[i] = new Vector.<uint>(len2+1);

     d[0][0]=0;

     var i:int;
     var j:int;

     for(i=1; i<=len1; ++i) d[i][0]=i; 
     for(i=1; i<=len2; ++i) d[0][i]=i;

     for(i = 1; i <= len1; ++i)
        for(j = 1; j <= len2; ++j)
           d[i][j] = Math.min( Math.min(d[i - 1][j] + 1,d[i][j - 1] + 1),
              d[i - 1][j - 1] + (tokens1[i - 1] == tokens2[j - 1] ? 0 : 1) );

     var nlevenshteinDist:Number = (d[len1][len2]) / (Math.max(len1, len2));

     return nlevenshteinDist;
  }

Надеюсь, это поможет!

Ответ 4

Реализация в D обобщается на любой диапазон и, следовательно, на массив. Таким образом, разделяя ваши предложения на массивы строк, их можно запустить через алгоритм, и будет предоставлен номер редактирования.

https://dlang.org/library/std/algorithm/comparison/levenshtein_distance.html

Ответ 5

Вот Java-реализация алгоритма редактирования расстояния для предложений с использованием подхода динамического программирования.

public class EditDistance {

    public int editDistanceDP(String sentence1, String sentence2) {
        String[] s1 = sentence1.split(" ");
        String[] s2 = sentence2.split(" ");
        int[][] solution = new int[s1.length + 1][s2.length + 1];

        for (int i = 0; i <= s2.length; i++) {
            solution[0][i] = i;
        }

        for (int i = 0; i <= s1.length; i++) {
            solution[i][0] = i;
        }

        int m = s1.length;
        int n = s2.length;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i - 1].equals(s2[j - 1]))
                    solution[i][j] = solution[i - 1][j - 1];
                else
                    solution[i][j] = 1
                            + Math.min(solution[i][j - 1], Math.min(solution[i - 1][j], solution[i - 1][j - 1]));
            }
        }
        return solution[s1.length][s2.length];
    }

    public static void main(String[] args) {
        String sentence1 = "first second third";
        String sentence2 = "second";
        EditDistance ed = new EditDistance();
        System.out.println("Edit Distance: " + ed.editDistanceDP(sentence1, sentence2));
    }
}