Сетевое различие между двумя строками в Javascript

Question

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

Клиент может вносить любые изменения в этот текст.

Что является самым эффективным в сети способом передачи разницы в результатах, которые понимает сервер? Кроме того, так как это будет происходить на стороне клиента (JavaScript), я также хотел бы, чтобы это было «быстрым» (или по крайней мере не заметно медленно)

Некоторые сценарии:

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

Я не могу использовать diff-подобный синтаксис, поскольку он неэффективен в сети, он проверяет строки, где примеры 1 и 3 будут давать ужасные отличия (особенно последний, где результат будет больше, чем сам старый).

У кого-нибудь есть опыт в этом вопросе? Пользователь работает на действительно большом наборе данных - около 3-5 МБ текста, а загрузка всего «нового» контента - это большой нет-нет.

Чтобы быть ясным, я ищу «протокол» передачи, сравнение строк не является проблемой.

Answer 1

Я не очень знаком с этой темой, но могу указать вам на проект с открытым исходным кодом (Apache License 2.0), который может быть очень полезен.

Это библиотека Diff, Match и Patch, написанная на нескольких языках, включая JavaScript, от инженера Google и используется в нескольких онлайн-службах совместного редактирования.

Вот список ресурсов:

• Diff, Match and Patch проект
• MobWrite проект (реализация редактор на основе вышеуказанного проекта)
• "Differential Synchronization" (A Google Tech Talk инженером)

Answer 2

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

Если у вас есть более простой алгоритм сравнения для работы (я не уверен, что именно вы подразумеваете под «сравнение строк не проблема»), вы также можете обнаружить перемещенные или скопированные фрагменты текста и отправить это как индекс начала и конца перемещенного или скопированного фрагмента текста, а также место назначения для его вставки.

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

Пример такого подхода см. В формате ed, который выводит diff -e. Это в основном вход, который можно было бы подавать в ed line-oriented text editor. Если вы хотите, чтобы абсолютная малая разница была отправлена, вы можете использовать индексирование на основе символов, а не линейную индексацию, но такой же базовый подход может работать.

Answer 3

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

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

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

Answer 4

Любые изменения, выполняемые пользователем, могут быть эффективно разбиты на: удалить из X для длины Y; вставить в текст X «что угодно». X и Y - смещения в символах с начала текста; Y - количество символов; «независимо» - любая строка символов. Вы говорите, что вам не нужна помощь при вычислении diff, но пример - here, за исключением того, что он богаче в своем выходе, чем вам нужно, но идентифицирует «удаления и вставки», поэтому просто измените выходную часть.

Точный формат, в котором вы отправляете данные на сервер, может быть настроен, но я не думаю, что в этом есть много пробега - ожидая измерения, я бы начал с отправки команд как D для удаления или I для вставки, числа в десятичной, вставленная строка в кавычках. Как только у вас есть статистика фактических передач, вы можете увидеть, сколько накладных расходов приходится на числа (десятичные или двоичные) и кавычки, но я подозреваю, что это может быть не все, что значимо (если это окажется, есть все виды вещей, которые вы можете попробовать, например, давать смещения от последней точки вставки или удаления, а не всегда с самого начала, чтобы ускорить работу).

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

Answer 5

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

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