Nano Hash - криптовалюты, майнинг, программирование

Самый быстрый способ найти расстояние редактирования слова, учитывая список миллионов слов

У меня есть файл с более чем миллионом слов, по одному слову в каждой строке. Я пытаюсь написать код, в котором, если бы мне дали слово, мне нужно было бы узнать, присутствует ли это слово в файле. Дело в том, что каждое слово нужно проверять 26^(word.length()-1) раз. Следовательно, просмотр каждого слова в файле не является хорошим решением. Я пытался найти алгоритмы в Интернете, но пока не нашел заметного ответа.

ИЗМЕНИТЬ Я думал как о HashMap, так и о Trie. Фактическая проблема здесь, скажем, у меня есть слово abc. Теперь моя задача состоит в том, чтобы добавить, удалить или заменить ровно одну букву в слове abc, чтобы создать слово X, а затем проверить, есть ли X в файле. Поэтому я смущен тем, какое решение может быть лучшим подходом.

java dictionary algorithm
02.05.2012

  • Вы выполняете поиск в определенной файловой системе/ОС или во многих? 02.05.2012
  • Простите меня за это, но было бы гораздо разумнее засунуть все ваши слова в базу данных (реляционную, ключ/значение, кэш памяти) и искать там. Вот для чего нужны базы данных 02.05.2012
  • @LeonardoCooper: Это всего лишь один файл, точнее текстовый файл. 02.05.2012
  • Пожалуйста, отредактируйте заголовок вашего вопроса. Это вводит в заблуждение, если вы действительно хотите найти расстояние редактирования между словарными словами. 02.05.2012

Ответы:


1

Вы можете построить дерево из слов в вашем файле. Это будет использовать гораздо меньше памяти, чем Hashset, и позволит вам проверить существование слова в O (количество символов в слове). Если память не имеет значения, конечно, Hashset подойдет (поскольку он встроен в него и требует гораздо меньше усилий).

02.05.2012
  • @noMAD: Вы пытаетесь рассчитать расстояние редактирования между словами словаря? 02.05.2012
  • Это решение с использованием дерева также должно быть хорошим подходом для поиска приблизительных совпадений с заданным запросом. Если вы проверяете дерево с помощью рекурсивной функции, вы можете использовать аргумент, который указывает, сколько правок вам разрешено. Каждый раз, когда вы спускаетесь по несоответствующей части дерева, вы уменьшаете это число. Это должен быть очень эффективный алгоритм. 02.05.2012

    • 2

    Сохраните слова в HashSet в памяти, и у вас будет O (1) поиск.

    02.05.2012
  • И что? String s = "abc"; String x = substituteOneLetter(s); return hashSet.contains(x);. Я что-то упускаю? 02.05.2012
  • Согласен - я не понимаю, как редактирование меняет пригодность хеш-таблицы. Я все еще думаю, что это лучшее решение! Не знаю, почему трие так любят :). Таким образом, +1 для вас, так как людям нравится ваш HashSet больше, чем моя HashTable. Достаточно справедливо - это, вероятно, немного лучше подходит! 02.05.2012
  • сложно реализовать хороший хэш-код, возможно, для миллионов разных строк; и поэтому обязательно будут столкновения, и O (1) не гарантируется. Таким образом, тройка или, что еще лучше, сжатая тройка (дерево суффиксов) даст вам O (размер строки поиска). 02.05.2012
  • К счастью, в классе String уже есть хорошая реализация hashCode, и вам не нужно реализовывать ее самостоятельно. 02.05.2012

    • 3

    Предположим, ваше слово «хам», и вы хотите найти все слова в пределах расстояния редактирования, равного 1.

    В этом случае можно сделать следующее.

    1) Сохраните словарные слова в HashMap. 2) Сгенерируйте все комбинации слов с расстоянием редактирования от 1 до «cad». 3) Для каждого из этих слов проверьте, присутствует ли это слово в HashMap.

    Поиск должен соответствовать таким словам, как «папа», «кот», «машина», «парень» и т. д.

    02.05.2012

    4

    Я бы построил хеш-таблицу, как вы читаете в файле со словами в нем. Вы должны быть в состоянии проверить, присутствует ли слово в постоянное время.

    02.05.2012

    5

    HashMap - это путь. Просто сохраните все слова в HashMap, а затем посмотрите карту, чтобы увидеть, существует ли ваше слово. Конечно, это полезно, только если вам нужно несколько поисков.

    Более практичное решение — записать HashMap на диск и загрузить его в память при следующем запуске приложения.

    02.05.2012

    6

    Табла имеет более быстрый способ

    FileInputStream inputStream = new FileInputStream("input.txt");
InputStreamReader streamReader = new InputStreamReader(inputStream, "UTF-8");
BufferedReader in = new BufferedReader(streamReader);
Map<String, Integer> map = new HashMap<String, Integer>();
for (String s; (s = in.readLine()) != null;) {
   ...
}
    02.05.2012

    7

    Другим решением может быть использование Фильтра Блума. Очень быстрая и компактная структура данных, используемая для проверки того, является ли элемент членом множества. Минусы в том, что это вероятностная структура данных, что означает, что возможны ложные срабатывания.

    Он работает, имея массив из m бит. При добавлении слова в фильтр это слово передается k различным хеш-функциям, устанавливающим биты в 1 в позициях, вычисленных этими хэшами. При запросе фильтра передайте слово тем же хэшам и проверьте, установлены ли биты в этих позициях. Если какой-либо из этих битов равен 0, это означает, что слово не существует в наборе, если все равны 1, необходим поиск, поскольку эти биты могли быть установлены при хэшировании других слов в те же позиции.

    02.05.2012
    Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..