Возможно ли сделать расстояние Левенштейна в Excel, не прибегая к макросам?

Question

Позволь мне объяснить.

Я должен выполнить нечеткое сопоставление для компании, поэтому в банкомате я использую калькулятор расстояний Левенштейна, а затем вычисляю процент сходства между двумя терминами. Если термины похожи более чем на 80%, Fuzzymatch возвращает "ИСТИНА".

Моя проблема в том, что я на стажировке и скоро уезжаю. Люди, которые будут продолжать это делать, не знают, как использовать Excel с макросами, и хотят, чтобы я реализовал то, что сделал, как мог.

Поэтому мой вопрос: как бы неэффективна эта функция, есть ли ЛЮБОЙ способ создать стандартную функцию в Excel, которая будет вычислять то, что я делал раньше, не прибегая к макросам?

Благодарю.

Answer 1

Если вы пришли об этом прибегая к помощи что-то вроде levenshtein distance google sheets

Я добавил это вместе с комментарием кода от milot-midia к этой сути ( https://gist.github.com/andrei-m/982927 - код под лицензией MIT)

• Из листов в верхнем меню, Tools -> Script Editor
• Назовите проект
  • Название функции (не проекта) позволит вам использовать функцию
• Вставьте следующий код

function Levenshtein(a, b) {
  if(a.length == 0) return b.length; 
  if(b.length == 0) return a.length;

  // swap to save some memory O(min(a,b)) instead of O(a)
  if(a.length > b.length) {
    var tmp = a;
    a = b;
    b = tmp;
  }

  var row = [];
  // init the row
  for(var i = 0; i <= a.length; i++){
    row[i] = i;
  }

  // fill in the rest
  for(var i = 1; i <= b.length; i++){
    var prev = i;
    for(var j = 1; j <= a.length; j++){
      var val;
      if(b.charAt(i-1) == a.charAt(j-1)){
        val = row[j-1]; // match
      } else {
        val = Math.min(row[j-1] + 1, // substitution
                       prev + 1,     // insertion
                       row[j] + 1);  // deletion
      }
      row[j - 1] = prev;
      prev = val;
    }
    row[a.length] = prev;
  }

  return row[a.length];
}

Вы должны быть в состоянии запустить его из электронной таблицы с

=Levenshtein(cell_1,cell_2)

Answer 2

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

Вот пример, который может обрабатывать строки длиной до 15 символов, его можно легко расширить для большего:

https://docs.google.com/spreadsheet/ccc?key=0AkZy12yffb5YdFNybkNJaE5hTG9VYkNpdW5ZOWowSFE&usp=sharing

Это не практично ни для чего, кроме специальных сравнений, но оно действительно показывает, как работает алгоритм.

Answer 3

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

Посмотрите на код здесь

Answer 4

На самом деле, я думаю, что я только что нашел обходной путь. Я добавил это в неправильной части кода...

Добавление этой строки

  } else if(b.charAt(i-1)==a.charAt(j) && b.charAt(i)==a.charAt(j-1)){
    val = row[j-1]-0.33;  //transposition

так что теперь читает

  if(b.charAt(i-1) == a.charAt(j-1)){
    val = row[j-1]; // match
  } else if(b.charAt(i-1)==a.charAt(j) && b.charAt(i)==a.charAt(j-1)){
    val = row[j-1]-0.33;  //transposition
  } else {
    val = Math.min(row[j-1] + 1, // substitution
                   prev + 1,     // insertion
                   row[j] + 1);  // deletion 
  } 

Кажется, чтобы решить проблему. Теперь "biulding" на 92% точнее, а "bilding" на 88%. (тогда как с оригинальной формулой 'biulding' был только 75%... несмотря на то, что он был ближе к правильному написанию здания)