Блог

Я довольно новичок в структурах данных, но я пытался реализовать эффективную функцию поиска по городу / автозаполнения города на серверной части моего приложения (сервер NodeJS express).

Изначально я загружал в память только массив городов (который составлял около 20 000 городов); я бы позволил своему клиентскому приложению выполнять поиск по городу через конечную точку /search и возвращал им список городов, которые соответствовали тому, что искал пользователь:

 import cities from './cities.json';

// Search endpoint
app.get('/search', (req, res) => {
  const results = [];
  const searchKey = req.body.key.toLowerCase();

  for (let city of cities) {
    if (city.toLowerCase().contains(searchKey)) {
      results.push(city);

      // Max 10 cities
      if (results.length > 10) {
        break;
      }
    }
  }

  res.json(cities);
});
  

Хотя это работает быстро, потому что у меня всего 20 000 городов, я предполагаю, что это довольно плохо с точки зрения временной сложности, поскольку сложность в худшем случае O(n) .

Итак, я думал о реализации словаря на основе дерева суффиксов, чтобы поиск ключа был бы сложным, O(m) m равным длине ключа (поправьте меня, если я ошибаюсь) за счет более высокой сложности пространства.

Но, как я уже сказал, я немного новичок во всем этом, поэтому мои вопросы:

1) Что обычно делается для реализации функции быстрого автозаполнения?

2) Было бы лучше, если бы я сохранял свои города в базе данных SQL? Есть ли способ эффективно настроить таблицу базы данных, чтобы обеспечить быстрый поиск на основе суффиксов?

Заранее спасибо!

Исходя из моего опыта, ElasticSearch может быть решением для автозаполнения. Она масштабируема и мощна. Некоторые рекомендуемые учебные пособия для чтения:

• https://hackernoon.com/elasticsearch-building-autocomplete-functionality-494fcf81a7cf
• https://qbox.io/blog/build-autocomplete-feature-using-elasticsearch-suggest => эта функция, использующая данные о городах в качестве примера, может подойти для вашего случая.

Вы также можете найти некоторую документацию по автозаполнению в их официальных документах:

https://www.elastic.co/guide/en/elasticsearch/guide/master/_index_time_search_as_you_type.html
— https://www.elastic.co/guide/en/elasticsearch/reference/6.6/search-suggesters-completion.html

Рассмотрите возможность использования автозаполнения (jquery UI) https://jqueryui.com/autocomplete