Вы всегда задумывались, как работает автодополнение, ну, в реальной жизни это очень сложно с машинным обучением и целой кучей вещей, происходящих в бэкэнде, которые я, очевидно, не могу построить сам! 😛
Итак, я решил создать довольно похожий рабочий прототип, который выполняет поиск по словарю английских слов примерно из 102 тыс. Слов (потому что это все, что я смог найти 😥) для создания предложений автозаполнения ..
Возможно, вы видите, что между словами нет корреляции, очевидно, потому что не используется машинное обучение, но основная цель здесь - иметь возможность завершить незаконченное слово (независимо, то есть независимо от того, что было набрано ранее).
Что ж, более чем завершение. Мне было больше любопытно, как работает back-text (прозрачный призрачный текст, завершающий ваш запрос) и как мне добавить свое предложение слова в само поле ввода.
Список слов отсюда. Репозиторий, состоящий из слов здесь.
Чтобы получить более точные предложения, я использовал показатель популярности, основанный на частоте использования английских слов, найденных здесь. (репозиторий здесь). Единственная проблема в том, что там всего около 10к слов, что неплохо!
Предварительные требования перед тем, как перейти к разделу кода:
- Знание синтаксиса JavaScript ES6 (классы, async / await)
- Структура данных Trie
- Добавление слушателей событий в DOM
- Знание о дребезге. Если не читать здесь.
А теперь давайте продолжим и закодируем это!
Шаг 1. Структура данных
Какую структуру данных мы выбираем и почему? Учитывая, что наш набор слов может быть действительно огромным (на данный момент всего около 102 тысяч), линейный поиск префиксов будет невозможен и нарушит работу пользователя с вашим приложением.
Хорошо известной структурой данных, используемой для поиска и сопоставления строк, является дерево Trie. Здесь важно отметить, что нужно следить за ограничением места, потому что в худшем случае, учитывая, что наши слова имеют только строчные буквы от a до z, могут потребляться примерно:
O (26 * средняя_длина_слов * число_слов)
[в зависимости от реализации вашего дерева]
Но положительным моментом является то, что временная сложность может быть довольно низкой - равной длине самой строки запроса.
O (длина_запроса)
Давайте закодируем это:
Мы создадим Trie класс, состоящий из методов для add новых слов и выработки предложений.
Давайте посмотрим, как добавить новые слова:
Давайте посмотрим на структуру более внимательно:
Рассмотрим слова ant & and, добавленные к дереву, вот как это будет выглядеть:
Затем нам нужен метод для поиска слова в дереве:
Затем мы будем использовать указанную выше find функцию для создания предложений:
Нам нужно пройти пространство поиска, в котором лежат наши предложения, и рекурсивно построить слово. Мы можем использовать поиск в глубину, чтобы просто пройти по каждому узлу и продолжить сцепление букв.
Мы можем контролировать количество дочерних узлов, которые будут проходить на первом узле, используя аргумент CHILDREN, чтобы предотвратить обход очень большого пространства, поскольку пространство поиска может быть очень большим для огромных корпусов слов.
Это все о кодировании нашей структуры данных, давайте теперь воспользуемся ее отображением предложений!
Давайте воспользуемся этим базовым HTML-кодом для визуализации поля ввода:
Я не включил сюда стили (вы можете увидеть скрипку здесь, чтобы просмотреть весь исходный код).
ЗАМЕТКА:
Имена файлов в приведенном выше gists не следует понимать буквально, у нас есть только 2 файла - index.html и index.js, весь JS-код находится в самом этом файле.
Теперь в нашем файле index.js, который также содержит наш класс Trie, мы добавим прослушиватели событий для обработки ввода в нашу панель поиска.
Двигаясь дальше, предполагая, что вы знаете, что такое debounce (короче говоря, наша main() функция вызывается, когда пользователь не набирает 250ms).
Причина добавления противодействия нашему main() методу:
Метод main() отвечает за извлечение предложений каждый раз, когда изменяется текст в строке поиска, но пользователь хочет, чтобы предложение появлялось только тогда, когда пользователь ожидает короткое время (200–250 мс) во время набора текста. Это не только улучшает взаимодействие с пользователем, но и сокращает количество ненужных вызовов функций метода main().
Давайте посмотрим на функцию main():
Здесь популярность - это мера частоты употребления слов в целом, например, слово the обычно встречается чаще, чем xylophone, верно?
Итак, метод getBestMatch() просто перебирает предложения и выбирает слово с наибольшей частотой.
Давайте разберемся в коде со схемой:
Вы можете видеть здесь, ghost, который является предложением, представляет собой не что иное, как элемент span, расположенный на расстоянии, равном ширине содержимого вашего запроса!
Как определить ширину содержания?
Сделайте еще один div с невидимым где-нибудь в DOM, в который вы можете записать содержимое запроса и измерить clientWidth!
HTML:
<div id='fake-div' class='div'></div>
JS:
const $fakeDiv = document.getElementById('fake-div');
const query = e.target.textContent.toLowerCase();
$fakeDiv.innerText = query;
CONTENT WIDTH = $fakeDiv.clientWidth
Просто правильно! Теперь просто поместите призрак $span в нужное место ...
Поскольку призрак $span должен быть похож на ввод текста в $input div, нам нужно имитировать некоторые свойства CSS $input div, а чтобы получить свойства CSS $input div, мы можем сделать это:
Теперь, чтобы установить style.left из $span, мы просто делаем:
LINE 33 : (main.js) GIST $span.style.left = r.left + $fakeDiv.clientWidth + 'px';
Осталось только одно! Заполните строку ввода, если пользователь хочет использовать данное предложение, например, если пользователь нажимает клавишу СТРЕЛКА ВПРАВО.
Большой! Вы дошли до конца этого блога! Обратите внимание, что я мог пропустить некоторые вещи, такие как получение данных из предоставленных URL-адресов, и сосредоточился больше на соответствующей теме, вы можете найти их по ссылке на исходный код ниже.
Вы можете поиграть с исходным кодом здесь.
И, как всегда, дайте мне знать в комментариях, если вы обнаружите что-то неправильное или если есть что-то, что вы хотите добавить! Ваше здоровье! 🍻
