2664002 - Способ и устройство для определения сходства, а также терминал

Способ и устройство для определения сходства, а также терминал

Иллюстрации

Показать все

Изобретение относится к области обработки текстов на естественных языках. Техническим результатом является более точное определение сходства между двумя строками символов. Способ определения сходства между строками символов включает выполнение разбиения на слова для первой строки символов и второй строки символов, соответственно, в результате чего получают первую последовательность и вторую последовательность, каждая из которых включает по меньшей мере одно слово; определение редакционного расстояния между первой строкой символов и второй строкой символов согласно заранее заданному алгоритму определения редакционного расстояния, первой последовательности и второй последовательности; и определение сходства между первой строкой символов и второй строкой символов согласно редакционному расстоянию и информации об операциях для преобразования первой последовательности во вторую последовательность. Для первой строки символов и второй строки символов выполняют, соответственно, разбиение на слова, в результате чего получают их разбиение на первую последовательность и вторую последовательность, и таким образом редакционное расстояние для преобразования первой строки символов во вторую строку символов определяют на основе отдельных слов в строке символов, вместо отдельных символов в строке символов. 2 н. и 14 з.п. ф-лы, 11 ил.

Реферат

Перекрестные ссылки на связанные заявки

[0001] Настоящая заявка ссылается на приоритет заявки на патент Китайской Народной Республики №201510882468.2, на которой она основана и которая была зарегистрирована 3 декабря 2015 г.. При этом содержание упомянутой заявки полностью включено в настоящий документ путем ссылки.

Область техники

[0002] Настоящее изобретение относится, в общем, к области обработки текстов на естественных языках, а именно, к способу и устройству для определения сходства, а также к терминалу.

Предпосылки создания изобретения

[0003] В области обработки текстов на естественных языках основная проблема - это создание способа определения сходства между строками символов, который мог бы найти применение во множестве различных сценариев применения, например, при кластеризации текстов или при извлечении информации и т.п. Соответственно, метод определения сходства между строками символов находится в фокусе интереса очень многих исследователей.

[0004] На существующем уровне развития техники сходство между строками символов определяют при помощи вычисления редакционного расстояния между двумя строками символов. А именно, две строки символов разбивают, соответственно, на отдельные символы; затем над символами одной из строк выполняют операции удаления, вставки или замены, чтобы преобразовать эту строку в другую строку символов; после чего вычисляют минимальное количество операций, необходимое для преобразования одной строки символов в другую, и это минимальное количество операций принимают за редакционное расстояние между двумя строками символов; наконец, в соответствии с редакционным расстоянием вычисляют сходство между двумя строками символов.

Сущность изобретения

[0005] В настоящем изобретении предложены способ и устройство для определения сходства, а также терминал.

[0006] В соответствии с первым аспектом настоящего изобретения предложен способ определения сходства, включающий:

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

определение редакционного расстояния между первой строкой символов и второй строкой символов согласно заранее заданному алгоритму определения редакционного расстояния, первой последовательности и второй последовательности; и

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

[0007] В соответствии со вторым аспектом вариантов осуществления настоящего изобретения предложено устройство для определения сходства, включающее:

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

первый модуль определения, сконфигурированный для определения редакционного расстояния между первой строкой символов и второй строкой символов согласно заранее заданному алгоритму определения редакционного расстояния, первой последовательности и второй последовательности; и

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

[0008] В соответствии с третьим аспектом вариантов осуществления настоящего изобретения предложен терминал, включающий:

процессор; и

память, сконфигурированную для хранения инструкций, исполняемых упомянутым процессором;

при этом процессор сконфигурирован:

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

для определения редакционного расстояния между первой строкой символов и второй строкой символов согласно заранее заданному алгоритму определения редакционного расстояния, первой последовательности и второй последовательности; и

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

[0009] Технические решения, предложенные в вариантах осуществления настоящего изобретения, позволяют, по меньшей мере частично, получить следующие полезные результаты:

[0010] для первой строки символов и второй строки символов выполняют, соответственно, разбиение на слова, в результате чего получают первую последовательность и вторую последовательно, и таким образом, редакционное расстояние для преобразования первой строки символов во вторую строку символов может быть определено на основе отдельных слов в первой последовательности и второй последовательности, вместо отдельных символов в первой строке символов и второй строке символов.

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

[0011] Нужно понимать, что и предшествующее общее описание, и подробное описание, приведенное ниже, являются исключительно иллюстративными и пояснительными и не ограничивают настоящее изобретение.

Краткое описание чертежей

[0012] На приложенных чертежах, которые входят в состав настоящего описания и являются его неотъемлемой частью, проиллюстрированы варианты осуществления, соответствующие настоящему изобретению. Приложенные чертежи, вместе с описанием, служат для разъяснения замысла настоящего изобретения.

[0013] Фиг. 1 представляет собой блок-схему алгоритма, иллюстрирующую способ определения сходства в соответствии с одним из примеров осуществления настоящего изобретения.

[0014] Фиг. 2 представляет собой блок-схему алгоритма, иллюстрирующую способ определения сходства в соответствии с одним из примеров осуществления настоящего изобретения.

[0015] Фиг. 3 представляет собой блок-схему, иллюстрирующую устройство для определения сходства в соответствии с одним из примеров осуществления настоящего изобретения.

[0016] Фиг. 4 представляет собой блок-схему, иллюстрирующую второй модуль определения в соответствии с одним из примеров осуществления настоящего изобретения.

[0017] Фиг. 5 представляет собой блок-схему, иллюстрирующую второй блок определения в соответствии с одним из примеров осуществления настоящего изобретения.

[0018] Фиг. 6 представляет собой блок-схему, иллюстрирующую второй блок определения в соответствии с одним из примеров осуществления настоящего изобретения.

[0019] Фиг. 7 представляет собой блок-схему, иллюстрирующую устройство для определения сходства в соответствии с одним из примеров осуществления настоящего изобретения.

[0020] Фиг. 8 представляет собой блок-схему, иллюстрирующую устройство для определения сходства в соответствии с одним из примеров осуществления настоящего изобретения.

[0021] Фиг. 9 представляет собой блок-схему, иллюстрирующую устройство для определения сходства в соответствии с одним из примеров осуществления настоящего изобретения.

[0022] Фиг. 10 представляет собой блок-схему, иллюстрирующую терминал в соответствии с одним из примеров осуществления настоящего изобретения.

[0023] Фиг. 11 представляет собой блок-схему, иллюстрирующую сервер в соответствии с одним из примеров осуществления настоящего изобретения.

Подробное описание изобретения

[0024] Далее настоящее изобретение будет описано более подробно с помощью конкретных примеров его осуществления, которые проиллюстрированы на приложенных чертежах. В приведенном ниже описании осуществляются ссылки на приложенные чертежи, где, если не указано обратное, аналогичными обозначениями на различных чертежах обозначены одинаковые или аналогичные элементы. Реализации примеров осуществления настоящего изобретения, изложенные в приведенном ниже описании, не являются всеми возможными реализациями, соответствующими настоящему изобретению. Напротив, они являются исключительно примерами устройств и способов, которые соответствуют аспектам, связанным с настоящим изобретением и изложенным в приложенной формуле изобретения.

[0025] В области обработки текстов на естественных языках основная проблема - это создание способа определения сходства между строками символов, который мог бы найти применение во множестве различных сценариев применения, например, в кластеризации текстов или при извлечении информации и т.п. В целях повышения точности определения сходства между двумя строками символов в вариантах осуществления настоящего изобретения предложен способ определения сходства. Фиг. 1 представляет собой блок-схему алгоритма, иллюстрирующую способ определения сходства в соответствии с одним из примеров осуществления настоящего изобретения, при этом способ определения сходства, предложенный в вариантах осуществления настоящего изобретения, может применяться в терминале. В соответствии с иллюстрацией фиг. 1, способ определения сходства, предложенный в вариантах осуществления настоящего изобретения, включает шаги, описанные ниже.

[0026] На шаге S101 выполняют разбиение на слова для первой строки символов и второй строки символов, соответственно, в результате чего получают первую последовательность и вторую последовательность, причем первая последовательность и вторая последовательность, каждая, включают по меньшей мере по одному слову.

[0027] На шаге S102 определяют редакционное расстояние между первой строкой символов и второй строкой символов согласно заранее заданному алгоритму определения редакционного расстояния, первой последовательности и второй последовательности.

[0028] На шаге 103 определяют сходство между первой строкой символов и второй строкой символов согласно редакционному расстоянию и информации о различных операциях для преобразования первой последовательности во вторую последовательность.

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

[0030] В еще одном из вариантов осуществления настоящего изобретения определение сходства между первой строкой символов и второй строкой символов согласно редакционному расстоянию и информации о различных операциях для преобразования первой последовательности во вторую последовательность включает:

получение информации об операции замены среди информации о различных операциях для преобразования первой последовательности во вторую последовательность;

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

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

[0031] В еще одном из вариантов осуществления настоящего изобретения определение сходства между первой строкой символов и второй строкой символов согласно редакционному расстоянию, количеству пар и стоимости различных операций, количеству слов в первой последовательности и количеству слов во второй последовательности, где упомянутые различные операции включают операцию замены и операцию перестановки, включает:

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

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

определение сходства между первой строкой символов и второй строкой символов согласно нормализованному результату.

[0032] В еще одном из вариантов осуществления настоящего изобретения определение сходства между первой строкой символов и второй строкой символов согласно редакционному расстоянию, количеству пар и стоимости различных операций, количеству слов в первой последовательности и количеству слов во второй последовательности, где упомянутые различные операции включают операцию замены, операцию перестановки, операцию вставки и операцию удаления, включает:

определение первого семантического редакционного расстояния между первой строкой символов и второй строкой символов согласно редакционному расстоянию, количеству пар, стоимости операции замены и стоимости операции перестановки;

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

определение сходства между первой строкой символов и второй строкой символов согласно первому семантическому редакционному расстоянию и второму семантическому редакционному расстоянию.

[0033] В еще одном из вариантов осуществления настоящего изобретения способ дополнительно включает:

определение стоимости операции замены и стоимости операции перестановки согласно соотношению между операцией замены и операцией перестановки; и

определение стоимости операции вставки, стоимости операции удаления и стоимости операции замены согласно соотношению между операцией замены, операцией вставки и операцией удаления.

[0034] В еще одном из вариантов осуществления настоящего изобретения способ дополнительно включает:

определение того, что стоимость операции замены, умноженная на 2, больше, чем стоимость операции перестановки, согласно соотношению между операцией замены и операцией перестановки; и

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

[0035] В еще одном из вариантов осуществления настоящего изобретения способ дополнительно включает:

определение того, что стоимость операции вставки равна стоимости операции удавления согласно соотношению между операцией вставки и операцией удаления.

[0036] В еще одном из вариантов осуществления настоящего изобретения определение редакционного расстояния между первой строкой символов и второй строкой символов согласно заранее заданному алгоритму определения редакционного расстояния, первой последовательности и второй последовательности включает:

где i-i-e слово в первой последовательности, j-j-e слово во второй последовательности; cost(S) - стоимость операции удаления, cost(C) - стоимость операции вставки, и cost(T) - стоимость операции замены.

[0037] В еще одном из вариантов осуществления настоящего изобретения определение минимального семантического редакционного расстояния между первой строкой символов и второй строкой символов согласно редакционному расстоянию, количеству пар, стоимости операции замены и стоимости операции перестановки включает:

где S1 и S2, соответственно, - первая строка символов и вторая строка символов, minCost(S1, S2) - минимальное семантическое редакционное расстояние, d - редакционное расстояние, р - количество пар, cost(J) - стоимость операции перестановки, cost(T) - стоимость операции замены и 2cost(T)-cost(J)>0.

[0038] В еще одном из вариантов осуществления настоящего изобретения определение первого семантического редакционного расстояния между первой строкой символов и второй строкой символов согласно редакционному расстоянию, количеству пар, стоимости операции замены и стоимости операции перестановки включает:

[0039] В еще одном из вариантов осуществления настоящего изобретения определение второго семантического редакционного расстояния между первой строкой символов и второй строкой символов согласно одному из следующего: стоимости операции вставки и стоимости операции удаления, стоимости операции замены, количеству слов в первой последовательности и количеству слов во второй последовательности, включает:

где normFact(S1, S2) - второе семантическое редакционное расстояние, n - количество слов в первой последовательности, m - количество слов во второй последовательности, cost(T) - стоимость операции замены, cost(S) - стоимость операции удаления и cost(C) - стоимость операции вставки.

[0040] В еще одном из вариантов осуществления настоящего изобретения определение сходства между первой строкой символов и второй строкой символов согласно первому семантическому редакционному расстоянию и второму семантическому редакционному расстоянию включает:

где sim(S1, S2) - сходство между первой строкой символов и второй строкой символов, minCost(S1, S2) - первое семантическое редакционное расстояние, и normFact(S1, S2) - второе семантическое редакционное расстояние.

[0041] Другие возможные варианты осуществления настоящего изобретения могут быть получены путем произвольного комбинирования любых из описанных выше опциональных технических решений и не будут подробно рассмотрены в настоящем документе.

[0042] На основе описания варианта осуществления настоящего изобретения, соответствующего фиг. 1, рассмотрим фиг. 2, которая представляет собой блок-схему алгоритма, иллюстрирующую способ определения сходства в соответствии с одним из примеров осуществления настоящего изобретения. При этом данный способ определения сходства может применяться в терминале. В соответствии с иллюстрацией фиг. 2, способ определения сходства, предложенный в вариантах осуществления настоящего изобретения, включает шаги, описанные ниже.

[0043] На шаге S201 выполняют разбиение на слова для первой строки символов и второй строки символов, соответственно, в результате чего получают первую последовательность и вторую последовательность.

[0044] Символы в строке символов могут быть не полностью независимыми, но имеющими отношение друг к другу. Некоторые из смежных строк символов могут быть неделимыми. К примеру, в строке «сегодня я собираюсь взобраться на Благоухающую гору », «сегодня » и «Благоухающую гору » являются неделимыми.

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

[0045] К примеру, когда первой строкой символов и второй строкой символов являются, соответственно, строки S1 и S2, первая последовательность и вторая последовательность будут иметь вид (S11, S12, S13, …, S1n) и (S21, S22, S23, …, S2m) соответственно. Количество слов в строке S1 равно n, а количество слов в строке S2 равно m.

[0046] Варианты осуществления настоящего изобретения не ограничены конкретными языками первой строки символов и второй строки символов. К примеру, обе строки символов, первая и вторая, могут представлять собой китайский язык, английский язык и т.п. При этом обе строки символов, первая и вторая, могут представлять собой грамматические предложения. К примеру, первой строкой символов может быть «сегодня я иду на Благоухающую гору », а второй строкой символов может быть «я иду на Благоухающую гору сегодня ».

[0047] На шаге S202 определяют стоимость операции замены и стоимость операции перестановки согласно соотношению между операцией замены и операцией перестановки, а также определяют стоимость операции вставки, стоимость операции удаления и стоимость операции замены согласно соотношению между операцией замены, операцией вставки и операцией удаления.

[0048] В традиционном способе определения сходства между строками символов, когда одну строку преобразуют в другую строку символов, используют, как правило, три операции редактирования, а именно: операцию вставки, операцию удаления и операцию замены, причем все три операции имеют одинаковую стоимость. Однако в строке символов некоторые из элементов могут встречаться в различных позициях строки символов и при этом не менять семантическое значение строки символов в целом. К примеру, три следующие строки символов: «сегодня я иду на Благоухающую гору », «я иду на Благоухающую гору сегодня » и «я сегодня иду на Благоухающую гору » имеют одно и то же значение, несмотря на то, что слова находятся в различных позициях строки символов. Соответственно, в вариантах осуществления настоящего изобретения, в дополнение к традиционным операциям вставки, удаления и замены, определена операция перестановки, а также определены различные стоимости для различных операций согласно соотношениям между этими различными операциями.

[0049] Варианты осуществления настоящего изобретения не ограничены в отношении конкретных значений стоимости различных операций. Однако при практической реализации операция перестановки может быть подразделена на две операции замены. Соответственно, в вариантах осуществления настоящего изобретения стоимость операции замены и стоимость операции перестановки могут быть определены согласно соотношению между операцией замены и операцией перестановки. К примеру, соотношение между стоимостью операции замены и стоимостью операции перестановки в вариантах осуществления настоящего изобретения может удовлетворять следующему выражению: 2 × стоимость операции замены > стоимость операции перестановки, а именно

где cost(T) - стоимость операции замены и cost(J) - стоимость операции перестановки.

[0050] Операция замены может быть подразделена на операцию удаления и операцию вставки. Соответственно, в вариантах осуществления настоящего изобретения стоимость операции вставки и стоимость операции удаления могут быть определены согласно соотношению между операцией замены, операцией вставки и операцией удаления. К примеру, соотношение между стоимостью операции замены, стоимостью операции перестановки и стоимостью операции удаления в вариантах осуществления настоящего изобретения может удовлетворять следующему выражению: стоимость операции вставки + стоимость операции удаления > стоимость операции замены. Также, может быть определено, что стоимость операции замены больше, чем максимальное значение стоимости операции вставки и стоимости операции удаления. К примеру, это соотношение может быть выражено следующей формулой:

где cost(S) - стоимость операции удаления и cost(C) - стоимость операции вставки.

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

[0052] На шаге S203 формируют заранее заданный алгоритм определения редакционного расстояния согласно стоимости операции замены, стоимости операции удаления и стоимости операции вставки.

[0053] К примеру, заранее заданный алгоритм определения редакционного расстояния может быть представлен формулой I.

где i-i-e слово в первой последовательности, j-j-e слово во второй последовательности; cost(S) - стоимость операции удаления, cost(C) - стоимость операции вставки и cost(T) - стоимость операции замены.

[0054] Из формулы I можно видеть, что заранее заданный алгоритм определения редакционного расстояния в вариантах осуществления настоящего изобретения может представлять собой алгоритм динамического программирования, при этом заранее заданный алгоритм определения редакционного расстояния может быть получен согласно стоимости операции удаления, стоимости операции вставки и стоимости операции замены, заранее заданным в вариантах осуществления настоящего изобретения.

[0055] Следует отметить, что шаги S202 и S203 - это шаги, которые выполняют перед определением сходства, но при этом их не нужно выполнять всякий раз, когда необходимо определить сходство между двумя строками символов, если гарантировано, что стоимость различных операций и заранее заданный алгоритм определения редакционного расстояния, уже определены перед определением сходства.

[0056] На шаге S204 определяют редакционное расстояние между первой строкой символов и второй строкой символов согласно заранее заданному алгоритму определения редакционного расстояния, первой последовательности и второй последовательности.

[0057] Под редакционным расстоянием между двумя строками символов понимают минимальное количество операций редактирования, необходимых для преобразования одной строки символов в другую, где каждая операция редактирования соответствует некоторой стоимости. За редакционное расстояние может быть принята общая стоимость преобразования. В вариантах осуществления настоящего изобретения операции редактирования, доступные для преобразования между строками символов, могут включать операцию замены, операцию вставки, операцию удаления и операцию перестановки.

[0058] На примере заранее заданного алгоритма определения редакционного расстояния по формуле 1, в вариантах осуществления настоящего изобретения, когда редакционное расстояние между первой строкой символов и второй строкой символов определяют согласно такому заранее заданному алгоритму определения редакционного расстояния, первой последовательности и второй последовательности, редакционное расстояние между первой строкой символов и второй строкой символов может быть определено при помощи рекурсивного вычисления на основе формулы I согласно заранее заданному алгоритму определения редакционного расстояния, первой последовательности и второй последовательности. Принцип вычисления редакционного расстояния на основе формулы I аналогичен принципу вычисления редакционного расстояния на основе существующих алгоритмов динамического программирования и, следовательно, не будет описан в вариантах осуществления настоящего изобретения более подробно.

[0059] На шаге S205, определяют сходство между первой строкой символов и второй строкой символов согласно редакционному расстоянию и информации о различных операциях для преобразования первой последовательности во вторую последовательность.

[0060] В вариантах осуществления настоящего изобретения информация о различных операциях для преобразования первой последовательности во вторую последовательность включает тип операции, количество операций каждого типа и стоимость операции каждого типа.

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

[0062] К примеру, если операции для преобразования первой строки символов во вторую строку символов включают две операции вставки, одну операцию удаления, одну операцию перестановки и одну операцию замены, редакционное расстояние d между первой строкой символов и второй строкой символов равно , когда сходство между первой строкой символов и второй строкой символов определяют согласно редакционному расстоянию, стоимости операции вставки, стоимости операции удаления, стоимости операции перестановки и стоимости операции замены.

[0063] К примеру, определение сходства между первой строкой символов и второй строкой символов согласно редакционному расстоянию и информации о различных операциях для преобразования первой последовательности во вторую последовательность включает, без ограничения перечисленным, шаги S2051-S2053, рассмотренные ниже.

[0064] На шаге S2051, после получения редакционного расстояния, получают информацию об операции замены среди информации о различных операциях для преобразования первой последовательности во вторую последовательность.

[0065] В ходе операции замены некоторое слово в первой строке символов заменяют на другое слово. В вариантах осуществления настоящего изобретения, при определении редакционного расстояния, выполняют статистический расчет на основе информации об операции замены в ходе преобразования, и информацию об операции замены записывают в заданный набор. В одном из вариантов осуществления настоящего изобретения информация об операции замены включает слово, замененное в ходе операции замены, и позицию замененного слова в соответствующей последовательности. Соответственно, данные, записанные в заданный набор, включают замененное слово и позицию замененного слова в первой последовательности. К примеру, если допустить, что первая строка символов представляет собой «я иду на Благоухающую гору сегодня », первой последовательностью будет «я - иду на - Благоухающую гору - сегодня ». Замененными словами будут «Благоухающую гору » и «иду на », а информация об операции замены, записанная в заданный набор, будет включать «иду на-2 , Благоухающую гору-5 ». Соответственно, при получении редакционного расстояния, информация об операции замены может быть получена из заданного набора, среди информации о различных операциях для преобразования первой строки символов во вторую строку символов, из заданного набора. А именно, эта информация включает слова, замененные в ходе различных операций замены и позиции каждого из замененных слов в первой последовательности.

[0066] При этом в вариантах осуществления настоящего изобретения дополнительно определяют операцию перестановки, согласно соотношению между операцией замены и операцией перестановки, которое заранее задано и соответствует выражению 2cost(T)-cost(J)>0. Соответственно, можно видеть, что стоимость двух операций замены больше, чем стоимость одной операции перестановки. Следовательно, когда есть возможность преобразовать первую строку символов во вторую строку символов при помощи одной операции перестановки, выполнение двух операций замены не является предпочтительным. Соответственно, в дополнение к замененным словам в первой последовательности и позициям каждого из замененных слов в первой последовательности, записанным в заданном наборе, может быть дополнительно определен факт наличия во второй последовательности каких-либо комбинаций из двух слов, входящих в заданный набор. Если во второй последовательности имеется хотя бы одна такая

Способ и устройство для определения сходства, а также терминал

Патент 2664002