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".

The 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