Как хранятся данные в текстовом поле?

Question

Я читал эту статью "Ropes: an Alternative to Strings" о ropes

[рисунком из the same paper]

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

Камеры используются где-то помимо текстовых полей?

---

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

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

Answer 1

Скорее всего, просто используйте любое текстовое поле, предоставляемое базовой ОС/системой окон. Я бы предположил, по крайней мере, самых случаях, это будет простой линейный массив для текстового поля - самый редко держите где-нибудь близко к количеству данных, необходимых для чего-либо вроде веревки, чтобы действительно иметь смысл.

Answer 2

Проблема (в простом случае) находит все строки, содержащие некоторую подстроку. Поскольку это не всегда поиск общих работ или даже писем, я предполагаю, что это будет какой-то индекс http://en.wikipedia.org/wiki/N-gram. Например, для триграмм:

1. Для каждой строки для индексации найдите все (переопределяющие) подпоследовательности из 3 символов (триграммы).
2. Для каждой подпоследовательности сохраните список всех строк, в которые он находится. Это индекс, и это карта из триграмм -> список строк.
3. Если пользователь вводит ключевое слово, найдите его триграммы, найдите их в индексе и верните пересечение соответствующих списков строк.

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

Браузеры могут улучшить это различными способами, например, если набрано несколько слов, они могут выполнять поиск каждого слова и возвращать URL-адреса, которые содержат.

Answer 3

Они используют алгоритм сопоставления префикса. Trie (и расширенные версии) - это наилучшие способы реализации наиболее длинных совпадений в префиксах.

Хром Источник: http://www.google.com/codesearch/p?hl=en#WT2nGdYBQUk/branches/chrome/chrome/src/cpp/include/chrome/browser/autocomplete/autocomplete.h&q=chromium%20lang:c++%20textbox&sa=N&cd=4&ct=rc&d=8

NB: Я предположил, что вы имели в виду, как они «помнят» текст, как вы печатаете.

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