node package manager
We need your input. Help make JavaScript better: Take the 2017 JavaScript Ecosystem survey »

breathalyzer

Breathalyzer

Проверка орфографии и нахождение минимального количества перестановок в словах с ошибкой

Описание методов увеличения производительности.

  1. Быстродействие оперативной памяти значительно превышает быстродействие файловой системы или СУБД. Поэтому первый шаг – загрузка словаря в оперативную память.
  2. Второй шаг – индексирование на основе теории баз данных. Необходимо для ускорения поиска. Индексом в предложенной реализации является длина слова. На каждой итерации выполнять поиск по всему словарю не нужно. Достаточно пройтись по ограниченной группе слов с определенной длиной.
  3. Вероятность нахождения минимального расстояния убывает со смещением от исходной длины слова. Поэтому итерации будут начинаться с поиска слов с такой же длиной, как у целевого, затем равномерно перемешаемся в оба направления от центра. Т. е. по принципу пирамиды.
  4. Предполагаю, что поиск слов, длина которых в 2 раза превышает длину исходного, не имеет смысла. Так как даже при полном расхождении в буквах минимальное расстояние будет найдено, до двукратного превышения длины.
  5. Если смещение от длины исходного слова равно расстоянию Левенштейна – то это минимальная длина. Переход на следующие итерации не имеет смысла.
  6. Что бы избежать повторного расчета минимальной длины, реализовано кеширование. Перед расчетом производится проверка слова в кеше (отдельном массиве).
  7. Смена регистра букв – емкая операция. Поэтому ее выполняем на строке во входном файле, а не у словаря.
  8. Использование более быстрых языковых конструкций. Например: расчет длины массива до цикла, а не на каждой его итерации и др. В целом, использование объектно-ориентированного подхода снижает производительность, но улучшает поддержку и читаемость кода. Поэтому важен баланс между производительностью и поддержкой.