Памятная фильтрация строк

Question

Допустим, у меня есть 500 слов:

Martin
Hopa
Dunam
Golap
Hugnog
Foo
... + 494 more words

У меня есть следующий текст размером около 85 КБ:

Мартинг пошел и взял егоСобственные вещи из магазина Hopa , и теперь он собирается положить их на хранение со своим лучшим другом Dunam .Они планируют использовать замок Golap , который они нашли в магазине Hugnog в Foo городе.>... text continues into several pages

Я хотел бы представить следующий текст:

------- пошел и взял у него вещи от ---- store, и теперь он собирается положить его на хранение вместе со своим лучшим другом ---- .Они планируют использовать замок ---- , который они нашли в ------ магазине в --- городе.>... text continues into several pages

В настоящее время я использую общий метод:

String[] 500words = //all 500 words
String[] maskFor500words = // generated mask for each word
String filteredText = StringUtils.replaceEach(textToBeFiltered, 500words , maskFor500words);

1. Есть ли другой способ сделать это, который может быть более эффективным, когда речь идет о памятии загрузка процессора?
2. Как лучше всего хранить 500 слов?Файл, список, перечисление, массив ...?
3. Как бы вы получили статистику, например, сколько и какие слова были заменены;и за каждое слово сколько раз его заменяли.

Answer 1

Мне было бы наплевать на использование процессора и памяти. Он должен быть относительно небольшим для такой проблемы и такого объема текста. Что бы я сделал, это

• имеет карту, содержащую все строки в качестве ключей, с числом раз, когда они были найдены в тексте (изначально 0)
• читать текст за словом, используя метод StringTokenizer или метод String.split ()
• для каждого слова найдите, содержит ли оно карту (операция O (1), очень быстрая)
• если он есть, добавьте «----» в StringBuilder и увеличьте значение, сохраненное для слова на карте
• еще добавить само слово (с пробелом перед, если это не первое слово текста)

В конце процесса StringBuilder содержит результат, а карта содержит число раз, когда каждое слово использовалось в качестве замены. Обязательно инициализируйте STringBuilder длиной исходного текста, чтобы избежать слишком большого перераспределения.

Должно быть простым и эффективным.

Answer 2

Мне было бы наплевать на память, но если вы это сделаете: trie - ваш друг.Это память эффективно для больших наборов и позволяет очень эффективное сопоставление.Возможно, вы захотите реализовать его в сжатом виде .

Answer 3

Если я правильно понимаю проблему, вам нужно прочитать 85 КБ текста и разобрать каждое слово (используйте split или StringTokenizer). Для каждого слова вам нужно знать, есть ли оно в наборе из 500 слов, и, если это так, заменить его соответствующей маской.

Если вы знаете, что у вас есть около 500 слов, я бы рекомендовал хранить 500 слов и их маски в HashMap с начальной емкостью около 650 (JDK говорит, что хеширование наиболее эффективно с коэффициентом загрузки 0,75). Вставьте пары «маска слова» в HashMap с помощью цикла for.

Самый большой удар за доллар (HashMap), который вы получаете, заключается в том, что операции get / put (поиск ключа) выполняются в постоянное время, что лучше, чем O (n) в массиве и даже O (log (n). )) если вы выполняете бинарный поиск по отсортированному массиву.

Вооружившись HashMap, вы можете создать SringBuffer, фильтруя эти 85 КБ текста. Верните String.toString () из вашего метода, и все готово! С уважением, - М.С.

PS Если вы строите карту на сервере и выполняете фильтрацию где-то еще (на клиенте), и вам необходимо перенести Словарь, HashMap этого не сделает - его нельзя сериализовать. Используйте Hashtable в этом случае. Если на той же машине, HashMap более эффективно использует память. Позже - М.С.