exponenta event banner

editDistance

Поиск расстояния между двумя строками или документами

Описание

пример

d = editDistance(str1,str2) возвращает наименьшее число вставок, удалений и замен графемы (термин Юникод для воспринимаемых человеком символов), необходимых для преобразования str1 кому str2.

пример

d = editDistance(document1,document2) возвращает наименьшее число вставок, удалений и замен маркеров, необходимых для преобразования document1 кому document2.

пример

d = editDistance(___,Name,Value) указывает дополнительные параметры, использующие один или несколько аргументов пары имя-значение.

Примеры

свернуть все

Найти расстояние редактирования между строками "Text analytics" и "Text analysis". Расстояние редактирования по умолчанию - это общее число вставок, удалений и замен графемы, необходимых для замены одной строки на другую.

str1 = "Text analytics";
str2 = "Text analysis";

Найдите расстояние редактирования.

d = editDistance(str1,str2)
d = 2

Это означает, что изменение первой строки на вторую требует двух правок. Например:

  1. Подстановка - подстановка символа "t" в "s": "Text analytics" кому "Text analysics".

  2. Удаление - удаление символа "c": "Text analysics" кому "Text analysis".

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

str1 = "It's time for breakfast.";
document1 = tokenizedDocument(str1);

str2 = "It's now time to sleep.";
document2 = tokenizedDocument(str2);

Найдите расстояние редактирования.

d = editDistance(document1,document2)
d = 3

Это означает, что изменение первого документа на второй требует трех правок. Например:

  1. Вставка - вставка слова "now".

  2. Подстановка - заменить слово "for" с "to".

  3. Подстановка - заменить слово "breakfast" с "sleep".

editDistance функция по умолчанию возвращает наименьшее число вставок, удалений и замен графемы, необходимых для изменения одной строки на другую. Чтобы включить действие подкачки в расчет, используйте 'SwapCost' вариант.

Сначала найдите расстояние редактирования между строками "MATALB" и "MATLAB".

str1 = "MATALB";
str2 = "MATLAB";
d = editDistance(str1,str2)
d = 2

Одно из возможных изменений:

  1. Заменить второй "A" с "L": ("MATALB" кому "MATLLB").

  2. Заменить второй "L" с "A": ("MATLLB" кому "MATLAB").

Значение по умолчанию для стоимости свопа (стоимость замены двух соседних графем): Inf. Это означает, что свопы не учитываются в направлении к расстоянию редактирования. Чтобы включить свопы, установите 'SwapCost' опция 1.

d = editDistance(str1,str2,'SwapCost',1)
d = 1

Это означает, что есть одно действие. Например, поменять местами смежные символы "A" и "L".

Чтобы вычислить расстояние редактирования между двумя словами и указать, что изменения не учитывают регистр, укажите пользовательскую функцию затрат на замену.

Сначала вычислите расстояние редактирования между строками "MATLAB" и "MathWorks".

d = editDistance("MATLAB","MathWorks")
d = 8

Это означает, что изменение первой строки на вторую требует восьми правок. Например:

  1. Подстановка - подстановка символа "A" с "a". ("MATLAB" кому "MaTLAB")

  2. Подстановка - подстановка символа "T" с "t". ("MaTLAB" кому "MatLAB")

  3. Подстановка - подстановка символа "L" с "h". ("MatLAB" кому "MathAB")

  4. Подстановка - подстановка символа "A" с "W". ("MathAB" кому "MathWB")

  5. Подстановка - подстановка символа "B" с "o". ("MathWB" кому "MathWo")

  6. Вставка - вставка символа "r". ("MathWo" кому "MathWor")

  7. Вставка - вставка символа "k". ("MathWor" кому "MathWork")

  8. Вставка - вставка символа "s". ("MathWork" кому "MathWorks")

Вычислить расстояние редактирования и указать пользовательскую функцию затрат на замену caseInsensitiveSubstituteCost, перечисленных в конце примера. Пользовательская функция caseInsensitiveSubstituteCost возвращает 0, если два входа одинаковы или отличаются только в зависимости от регистра, в противном случае возвращает 1.

d = editDistance("MATLAB","MathWorks",'SubstituteCost',@caseInsensitiveSubstituteCost)
d = 6

Это означает, что общая стоимость смены первой строки на вторую равна 6. Например:

  1. Замещение (стоимость 0) - замена символа "A" с "a". ("MATLAB" кому "MaTLAB")

  2. Замещение (стоимость 0) - замена символа "T" с "t". ("MaTLAB" кому "MatLAB")

  3. Замена (стоимость 1) - замена символа "L" с "h". ("MatLAB" кому "MathAB")

  4. Замена (стоимость 1) - замена символа "A" с "W". ("MathAB" кому "MathWB")

  5. Замена (стоимость 1) - замена символа "B" с "o". ("MathWB" кому "MathWo")

  6. Вставка (стоимость 1) - вставка символа "r". ("MathWo" кому "MathWor")

  7. Вставка (стоимость 1) - вставка символа "k". ("MathWor" кому "MathWork")

  8. Вставка (стоимость 1) - вставка символа "s". ("MathWork" кому "MathWorks")

Пользовательская функция затрат

Пользовательская функция caseInsensitiveSubstituteCost возвращает 0, если два входа одинаковы или отличаются только в зависимости от регистра, в противном случае возвращает 1.

function cost = caseInsensitiveSubstituteCost(grapheme1,grapheme2)

if lower(grapheme1) == lower(grapheme2)
    cost = 0;
else
    cost = 1;
end

end

Входные аргументы

свернуть все

Исходная строка, заданная как строковый массив, символьный вектор или клеточный массив символьных векторов.

Если str1 содержит несколько строк, затем str2 должен быть того же размера, что и str1 или скаляр.

Типы данных: char | string | cell

Целевая строка, заданная как строковый массив, символьный вектор или клеточный массив символьных векторов.

Если str2 содержит несколько строк, затем str1 должен быть того же размера, что и str2 или скаляр.

Типы данных: char | string | cell

Исходный документ, указанный как tokenizedDocument массив.

Если document1 содержит несколько документов, затем document2 должен быть того же размера, что и document1 или скаляр.

Целевой документ, указанный как tokenizedDocument массив.

Если document2 содержит несколько документов, затем document1 должен быть того же размера, что и document2 или скаляр.

Аргументы пары «имя-значение»

Укажите дополнительные пары, разделенные запятыми Name,Value аргументы. Name является именем аргумента и Value - соответствующее значение. Name должен отображаться внутри кавычек. Можно указать несколько аргументов пары имен и значений в любом порядке как Name1,Value1,...,NameN,ValueN.

Пример: editDistance("MATALB","MATLAB",'SwapCost',1) возвращает расстояние редактирования между строками "MATALB" и "MATLAB" и устанавливает стоимость замены двух соседних графем равной 1.

Стоимость вставки графемы или маркера, указанного как разделенная запятыми пара, состоящая из 'InsertCost' и неотрицательный скаляр или дескриптор функции.

Если 'InsertCost' является дескриптором функции, то функция должна принять один ввод и возвратить затраты на вставку ввода в источник. Например:

  • Для ввода строки в editDistance, функция затрат должна иметь форму cost = func(grapheme), где функция возвращает стоимость вставки grapheme в str1.

  • Для ввода документа в editDistance, функция затрат должна иметь форму cost = func(token), где функция возвращает стоимость вставки token в document1.

Пример: 'InsertCost',2

Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | function_handle

Стоимость удаления графемы или маркера, указанного как пара, разделенная запятыми, состоящая из 'DeleteCost' и неотрицательный скаляр или дескриптор функции.

Если 'DeleteCost' является дескриптором функции, то функция должна принять один ввод и возвратить стоимость удаления ввода из источника. Например:

  • Для ввода строки в editDistance, функция затрат должна иметь форму cost = func(grapheme), где функция возвращает стоимость удаления grapheme от str1.

  • Для ввода документа в editDistance, функция затрат должна иметь форму cost = func(token), где функция возвращает стоимость удаления token от document1.

Пример: 'DeleteCost',2

Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | function_handle

Стоимость замены графемы или маркера, указанного как разделенная запятыми пара, состоящая из 'SubstituteCost' и неотрицательный скаляр или дескриптор функции.

Если 'SubstituteCost' является дескриптором функции, то функция должна принимать ровно два входа и возвращать стоимость замены первого входа вторым в источнике. Например:

  • Для ввода строки в editDistance, функция затрат должна иметь форму cost = func(grapheme1,grapheme2), где функция возвращает стоимость замены grapheme1 с grapheme2 в str1.

  • Для ввода документа в editDistance, функция затрат должна иметь форму cost = func(token1,token2), где функция возвращает стоимость замены token1 с token2 в document1.

Пример: 'SubstituteCost',2

Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | function_handle

Стоимость замены двух соседних графем или маркеров, указанных как разделенная запятыми пара, состоящая из 'SwapCost' и неотрицательный скаляр или дескриптор функции.

Если 'SwapCost' является дескриптором функции, то функция должна принимать ровно два входа и возвращать стоимость замены первого входа на второй в источнике. Например:

  • Для ввода строки в editDistance, функция затрат должна иметь форму cost = func(grapheme1,grapheme2), где функция возвращает стоимость замены соседних графем grapheme1 и grapheme2 в str1.

  • Для ввода документа в editDistance, функция затрат должна иметь форму cost = func(token1,token2), где функция возвращает стоимость замены смежных маркеров token1 и token2 в document1.

Пример: 'SwapCost',2

Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | function_handle

Выходные аргументы

свернуть все

Редактировать расстояние, возвращаемое как неотрицательный скаляр.

Алгоритмы

свернуть все

Изменить расстояние

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

Для других часто используемых расстояний редактирования используйте следующие опции:

РасстояниеОписаниеВарианты
Левенштейн (по умолчанию)наименьшее число вставок, удалений и заменДефолт
Дамерау-Левенштейннаименьшее количество вставок, удалений, замен и свопов'SwapCost',1
Хэммингтолько наименьшее число замен'InsertCost',Inf,'DeleteCost',Inf

Представлен в R2019a