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

Question

Существует ли алгоритм, позволяющий найти расстояние редактирования на уровне слов между двумя предложениями? Например, «Большая толстая собака» и «Большой дом с толстой собакой» имеют 1 замену, 3 вставки

Answer 1

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

Вот пример реализации идеи @ 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;
  }

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