Какой лучший (основанный на словах или символах) алгоритм сравнения?

Question

Итак, я хочу иметь возможность находить различия между двумя строками для каждого слова (может быть, быстрее, чем для каждого символа, хотя, если для каждого символа быстрее, я бы хотел сделать это таким образом) .

Вот пример того, чего я хочу достичь: Исходный текст:

Hello there!

Модифицированный текст:

Helay scere?

дифф:

Hel[lo](ay) [th](sc)ere[!](?)

• текст в скобках - это то, что было удалено, текст в скобках - это то, что было добавлено

существует своего рода супер-хакерский способ сделать это с помощью инструмента командной строки, например opendiff , но он требует символа новой строки между каждым символом, поскольку opendiff основан на строках.

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

спасибо.

Answer 1

Посмотрите на https://github.com/pvande/differ. Этот камень делает то, что вы ищете

Answer 2

Итак, вы можете многократно использовать LCS (как указано выше), чтобы найти все общие строки и удалить их из обеих ваших строк, заменив их другой строкой - скажем просто «*». Затем вы выполняете итерацию по обеим строкам одновременно и повторно комбинируете общее и отличное обратно вместе.

Пример

A) Hello there!
B) Helay scere?

LCS detection gives us ["Hel"," ","ere"], and after replacement we have
A) *lo*th*!
B) *ay*sc*?

Now you split on the delimiter ("*") giving you
A) ["lo","th","!"]
B) ["ay","sc","?"]

И отсюда вы просто идете делать простую сетку. Ключевым моментом, который стоит отметить, является то, что могут быть нулевые записи, например, если вы используете этот метод для «Ада» и «Хела», вы в конечном итоге получите

Common LCS) ["Hel"]
A) ["l"]
B) [""]

meaning your result will be Hel[l]() 

Надеюсь, это приемлемо.

Answer 3

Вы можете проверить это: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem. Это не сложно реализовать.

Answer 4

Вот рубиновый драгоценный камень, который различает строки: http://rubydoc.info/gems/diff-lcs/1.1.3/frames

Перед раздачей я только что сделал (в irb)

require 'rubygems'
require 'diff/lcs'
require 'diff/lcs/array'
require 'diff/lcs/string'

Таким образом, написание логики для вставки, удаления встроенных и вставленных маркеров становится тривиальным благодаря этому массиву изменений 2D.

Хотя я не уверен, что это лучший способ.

Answer 5

Решением будет найти расстояние редактирования между строками.