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

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

0 голосов
/ 24 августа 2010

Я читал эту статью "Веревки: альтернатива струнам" о веревках

alt text

[ рисунок из той же бумаги ]

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

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

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

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

Ответы [ 3 ]

1 голос
/ 24 августа 2010

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

0 голосов
/ 24 августа 2010

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

Chrome Источник: 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

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

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

0 голосов
/ 24 августа 2010

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

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

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

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

...