Как данные хранятся в текстовом поле?
Я читал эту статью "Веревки: альтернатива струнам" о веревках
[ рисунок из той же бумаги ]
и мне было интересно, если это структура данных, используемая современными браузерами для реализации текстовых полей или нет. Используем ли мы для этого веревки или другие структуры данных?
Используются ли где-нибудь веревки, кроме текстовых полей?
Предыдущий заголовок моего вопроса как-то также означал, что я хотел знать, как происходит "запоминание" строки - когда я набираю текст, я получаю предложения. Я изменил это сейчас.
Я хочу знать, какая структура данных используется для хранения строки, когда я ее набираю. Это что-то простое, например, массив символов или что-то сложное, например, веревка?
3 ответа
Скорее всего, просто используйте любое текстовое поле, предоставляемое базовой ОС / оконной системой. Я предполагаю, что, по крайней мере, в большинстве случаев это будет простой линейный массив для текстового поля - чаще всего он хранится где-то близко к количеству данных, необходимых для чего-то вроде веревки, чтобы действительно иметь смысл.
Проблема (в простом случае) - найти все строки, содержащие некоторую подстроку. Так как поиск не всегда выполняется по обычным работам или даже по письмам, я думаю, что это будет своего рода индекс http://en.wikipedia.org/wiki/N-gram. Например, для триграмм:
- Для каждой строки для индекса найдите все (пересекающиеся) подпоследовательности из 3 символов (триграмм).
- Для каждой подпоследовательности сохраните список всех строк, в которых она появляется. Это индекс и карта из триграммы -> список строк.
- Если пользователь вводит ключевое слово, находит его триграммы, ищет их в индексе и возвращает пересечение соответствующих списков строк.
Это быстрый способ вернуть строки, которые могут содержать слово. Для большей точности результаты могут быть отфильтрованы до тех, которые содержат всю подстроку.
Браузеры могут улучшить это различными способами, например, если введено несколько слов, они могут выполнить поиск по каждому слову и вернуть URL-адреса, которые содержат либо.
Они используют алгоритм сопоставления префиксов. Trie (и его расширенные версии) являются лучшими способами реализации самых длинных префиксных совпадений.
NB: Я предположил, что вы имели в виду, как они "запоминают" текст при вводе текста.
Если вы имеете в виду, как каждое текстовое поле содержит список вещей, которые вы набрали ранее, и показывает его во всплывающем окне - список, который добавляется к каждому при "отправке" этого текста.