Измерение идентичности строк (в Javascript)

Question

В принципе на этот вопрос можно ответить независимо от языка, но в частности я ищу реализацию Javascript.

Существуют ли библиотеки, которые позволяют мне измерять «идентичность» двух строк? В общем, есть ли какие-либо алгоритмы, которые делают это, что я мог бы реализовать (в Javascript)?

Возьмем, к примеру, следующая строка

Аномальные Эластичность монокристаллического Magnesiosiderite через спиновый переход в нижней мантии Земли

А также рассмотрим следующее, слегка скорректированы строка. Обратите внимание на выделенные жирным шрифтом части, которые отличаются

B НОРМАЛЬНО Эластичность Sin гле Cry СТАЛЬ Магне SIO-Sid erite через S пин-Tra nsition в Eart вс Нижняя Mant ле.

Собственные операторы равенства Javascript не расскажут вам о связи между этими строками. В этом конкретном случае вы можете сопоставлять строки, используя регулярное выражение, но в целом это работает только тогда, когда вы знаете, какие различия ожидать. Если входные строки являются случайными, общность этого подхода быстро разрушается.

подход ... я могу себе представить, писать алгоритм, который расщепляет до входной строки в произвольном количестве N подстрок, а затем соответствие целевой строки со всеми этими подстроками, и используя количество матчей в качестве измерения идентичности. Но это похоже на непривлекательный подход, и я даже не хочу думать о том, насколько большой O будет зависеть от N.

Мне кажется, что в таком алгоритме есть много свободных параметров. Например, независимо от чувствительности к регистру символов, должен вносить свой вклад в равной степени/больше/меньше для измерения, чем порядок-сохранение символов, кажется, произвольного выбора, чтобы дизайнер, то есть:

identicality("Abxy", "bAxy") против identicality("Abxy", "aBxy")

Определение требований к конкретному ... Первый пример - это сценарий, в котором я мог бы его использовать. Я загружаю кучу строк (заголовки научных статей), и я проверяю, есть ли у меня в моей базе данных. Тем не менее, источник может содержать опечатки, различия в соглашениях, ошибки, что угодно, что затрудняет сопоставление. Вероятно, есть более простой способ сопоставления названий в этом конкретном сценарии: поскольку вы можете ожидать, что может пойти не так, это позволяет вам записать некоторого зверя регулярного выражения.

Answer 1

Вы можете осуществить Hirschberg's algorithm и отличить delete/insert операции
(или изменить Levenshtein).

Для Hirschbers("Abxy", "bAxy")results are:

It was 2 edit operations: 
keep: 3 
insert: 1 
delete: 1 

и Hirschbers("Abxy", "aBxy")results are:

It was 2 edit operations: 
keep: 2 
replace: 2 

Вы можете проверить реализацию javascript на this page.

'оптимальное' Стринг-Alignment Расстояние

function optimalStringAlignmentDistance(s, t) { 
 
    // Determine the "optimal" string-alignment distance between s and t 
 
    if (!s || !t) { 
 
    return 99; 
 
    } 
 
    var m = s.length; 
 
    var n = t.length; 
 
    
 
    /* For all i and j, d[i][j] holds the string-alignment distance 
 
    * between the first i characters of s and the first j characters of t. 
 
    * Note that the array has (m+1)x(n+1) values. 
 
    */ 
 
    var d = new Array(); 
 
    for (var i = 0; i <= m; i++) { 
 
    d[i] = new Array(); 
 
    d[i][0] = i; 
 
    } 
 
    for (var j = 0; j <= n; j++) { 
 
    d[0][j] = j; 
 
    } 
 
     
 
    // Determine substring distances 
 
    var cost = 0; 
 
    for (var j = 1; j <= n; j++) { 
 
    for (var i = 1; i <= m; i++) { 
 
     cost = (s.charAt(i-1) == t.charAt(j-1)) ? 0 : 1; // Subtract one to start at strings' index zero instead of index one 
 
     d[i][j] = Math.min(d[i][j-1] + 1,     // insertion 
 
         Math.min(d[i-1][j] + 1,   // deletion 
 
            d[i-1][j-1] + cost)); // substitution 
 
         
 
     if(i > 1 && j > 1 && s.charAt(i-1) == t.charAt(j-2) && s.charAt(i-2) == t.charAt(j-1)) { 
 
     d[i][j] = Math.min(d[i][j], d[i-2][j-2] + cost); // transposition 
 
     } 
 
    } 
 
    } 
 
    
 
    // Return the strings' distance 
 
    return d[m][n]; 
 
} 
 

 
alert(optimalStringAlignmentDistance("Abxy", "bAxy")) 
 
alert(optimalStringAlignmentDistance("Abxy", "aBxy"))

Damerau-Левенштейна Расстояние

function damerauLevenshteinDistance(s, t) { 
 
    // Determine the Damerau-Levenshtein distance between s and t 
 
    if (!s || !t) { 
 
    return 99; 
 
    } 
 
    var m = s.length; 
 
    var n = t.length;  
 
    var charDictionary = new Object(); 
 
    
 
    /* For all i and j, d[i][j] holds the Damerau-Levenshtein distance 
 
    * between the first i characters of s and the first j characters of t. 
 
    * Note that the array has (m+1)x(n+1) values. 
 
    */ 
 
    var d = new Array(); 
 
    for (var i = 0; i <= m; i++) { 
 
    d[i] = new Array(); 
 
    d[i][0] = i; 
 
    } 
 
    for (var j = 0; j <= n; j++) { 
 
    d[0][j] = j; 
 
    } 
 
    
 
    // Populate a dictionary with the alphabet of the two strings 
 
    for (var i = 0; i < m; i++) { 
 
    charDictionary[s.charAt(i)] = 0; 
 
    } 
 
    for (var j = 0; j < n; j++) { 
 
    charDictionary[t.charAt(j)] = 0; 
 
    } 
 
    
 
    // Determine substring distances 
 
    for (var i = 1; i <= m; i++) { 
 
    var db = 0; 
 
    for (var j = 1; j <= n; j++) { 
 
     var i1 = charDictionary[t.charAt(j-1)]; 
 
     var j1 = db; 
 
     var cost = 0; 
 
     
 
     if (s.charAt(i-1) == t.charAt(j-1)) { // Subtract one to start at strings' index zero instead of index one 
 
     db = j; 
 
     } else { 
 
     cost = 1; 
 
     } 
 
     d[i][j] = Math.min(d[i][j-1] + 1,     // insertion 
 
         Math.min(d[i-1][j] + 1,  // deletion 
 
            d[i-1][j-1] + cost)); // substitution 
 
     if(i1 > 0 && j1 > 0) { 
 
     d[i][j] = Math.min(d[i][j], d[i1-1][j1-1] + (i-i1-1) + (j-j1-1) + 1); //transposition 
 
     } 
 
    } 
 
    charDictionary[s.charAt(i-1)] = i; 
 
    } 
 
     
 
    // Return the strings' distance 
 
    return d[m][n]; 
 
} 
 

 
alert(damerauLevenshteinDistance("Abxy", "aBxy")) 
 
alert(damerauLevenshteinDistance("Abxy", "bAxy"))

Optimal String Alignment имеет более performance

Оптимальное выравнивание строк Расстояние 0.20-0.30ms
Damerau-Левенштейна Расстояние 0.40-0.50ms