Самый быстрый способ / алгоритм, чтобы найти одно другое ключевое слово между двумя наборами текстовых файлов - PullRequest
Новая
       3

Самый быстрый способ / алгоритм, чтобы найти одно другое ключевое слово между двумя наборами текстовых файлов

1 голос
/ 05 апреля 2009

У меня есть 4 текстовых файла, 2 из них содержат ключевое слово, которого нет у 2 других текстовых файлов.

Какой самый быстрый способ / алгоритм для нахождения этого «ключевого слова» в первых двух текстовых файлах, но не существует в двух других файлах?

Я могу придумать очень медленные способы, такие как переход от слова к слову, а затем поиск с помощью IndexOf и т. Д. Но звучит так, как будто это будет очень медленно. Особенно, если номер файла увеличивается.

Доп. 1: Ключевыми словами может быть одно слово, например «яблоко», или предложение «Вы видели яблоню?». Как только два других текстовых файла не содержат это ключевое слово, это не имеет значения. Но я предполагаю, что производительность будет короче.

Extra 2: Эти текстовые файлы на самом деле являются простыми источниками HTML, поэтому ожидается, что они будут большими.

Ответы [ 3 ]

4 голосов
/ 05 апреля 2009

Если у вас есть только одно ключевое слово (или ключевая фраза), то вам, скорее всего, лучше всего использовать indexOf () или аналогичные простые вызовы существующих функций. Ваше узкое место не будет процессором или даже пропускной способностью памяти, это просто скорость диска. Ваш процессор может искать в 10 раз быстрее, чем диск может его подавать.

Если у вас есть файлы , уже находящиеся в памяти , и вам необходимо быстро выполнить сканирование, вероятный алгоритм вероятен Бойер-Мур KMP . Но даже не думайте сначала, попробуйте простые примитивы типа indexOf () и посмотрите, действительно ли это слишком медленно для вас или нет. Компьютеры БЫСТРО, и вы, вероятно, будете удивлены.

2 голосов
/ 05 апреля 2009

Казалось бы, для такой вещи идеально подходит хеш-таблица. Хранение и извлечение записей хеш-таблицы возможно за время O (1) и может использоваться здесь довольно эффективно. Я бы порекомендовал попробовать что-то вроде следующего алгоритма:

  1. Создайте Dictionary<string, int> (это по сути универсальная хеш-таблица, доступная в .NET 2.0 и более поздних версиях). Это будет использоваться для отслеживания вхождений каждого ключевого слова (значение будет действовать как битовое поле).

  2. Загрузите каждый текстовый файл и прочитайте все ключевые слова, установив соответствующий бит для соответствующего текстового файла, в котором найдено ключевое слово. Пример: 

    dict[keyword] |= (1 << curTextFileIndex);

    , где curTextFileIndex будет варьироваться от 0 до 3 в вашем случае.

  3. Перебирать все записи в словаре в поисках подходящего значения (битовое поле). В вашем случае, так как вы ищете ключевое слово, которое появляется в первых двух файлах, но , а не в последних двух , значение, которое вы хотите найти, равно 0011 (или 3 в десятичном виде). ). Найдите эту запись, и у вас будет ключевое слово.

Если я не ошибаюсь, этот алгоритм выполняется за время O (n), где n - общее количество ключевых слов во всех ваших текстовых файлах. Я не думаю, что тебе станет лучше, если честно.

Надеюсь, это поможет. Дайте мне знать, если вам нужно больше подробностей ...

Редактировать : Хммм ... Кажется, я пропустил бит о ваших "ключевых словах", возможно, содержащих более одного фактического слова. Если известно, что эти «ключевые слова» короче определенного (низкого) числа слов, то я думаю, что это решение все еще может быть жизнеспособным с небольшими изменениями. В противном случае, вам понадобится что-то более умное, оно появится.

1 голос
/ 05 апреля 2009

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

Теперь создайте набор или хэш-набор (в основном, он позволяет очень быстро проверить, является ли строка частью коллекции) ключевых слов для каждого файла. (Google для кода / деталей, они практически на каждом языке)

После того, как это будет сделано, все, что вам нужно сделать, - это перебрать все возможные ключевые слова и проверить, присутствует ли оно точно в 2 файлах. Поскольку вы используете хэш-набор, каждый поиск займет всего несколько операций, поэтому в целом это должно быть довольно быстро.

...