Что такое хорошая структура данных для сохранения словаря?

Question

Я разрабатываю фильтр слов, который может отфильтровывать плохие слова (200 слов в списке) в статье (около 2000 слов). И там у меня есть проблема, что то, что data structure Мне нужно сохранить этот неверный список слов, чтобы программа могла использовать немного времени, чтобы найти плохие слова в статьях?

- больше деталей

Если размер списка плохих слов является 2000, статья 50 тысяч, и программа будет процедура около 1000 статей один раз. Какая структура данных Я должен выбрать, менее решение O (n^2) в поиске?

Answer 1

думаю лучший структура, вы можете использовать есть set. - http://en.wikipedia.org/wiki/Set_%28abstract_data_type%29

Я принимаю log_2(n) время, чтобы добавить элемент в структуру (однократная операция) и тот же ответ на каждый запрос. Поэтому, если у вас будет 200 элементов в структуре данных, вашей программе необходимо будет выполнить только около 8 операций для проверки, существует ли это слово в set.

Answer 2

Вы можете использовать HashTable, потому что его средняя сложность - O (1) для вставки и поиска, а ваши данные - всего 2000 слов. http://en.wikipedia.org/wiki/Hash_table

Answer 3

словарь обычно это отображение одной вещи (слово в 1-ом языке) на другое (слово во 2-ом языке). Вам, похоже, не нужно это отображение здесь, а просто набор слов.

В большинстве языков предоставляется набор структура данных из коробки, которая имеет insert и методы тестирования членства.

Небольшой пример в Python, сравнивая list и set:

import random 
import string 
import time 

def create_word(min_len, max_len): 
    return "".join([random.choice(string.ascii_lowercase) for _ in 
        range(random.randint(min_len, max_len+1))]) 

def create_article(length): 
    return [create_word(3, 10) for _ in range(length)] 

wordlist = create_article(50000) 
article = " ".join(wordlist) 
good_words = [] 
bad_words_list = [random.choice(wordlist) for _ in range(2000)] 

print("using list") 
print(time.time()) 
for word in article.split(" "): 
    if word in bad_words_list: 
     continue 
    good_words.append(word) 

print(time.time()) 

good_words = [] 
bad_words_set = set(bad_words_list) 

print("using set") 
print(time.time()) 
for word in article.split(" "): 
    if word in bad_words_set: 
     continue 
    good_words.append(word) 

print(time.time()) 

Это создает «статью» 50000 случайно созданных «слов» с длиной от 3 до 10 букв, а затем улавливает 2000 эти слова как «плохие слова».

Во-первых, они помещаются в list, а «статья» отсканирована слово за словом, если слово in этот список плохих слов. В Python оператор in тестирует членство. Для неупорядоченного списка нет лучшего способа сканирования всего списка.

Второй подход использует тип данных set, который инициализируется списком плохих слов. A set не имеет заказа, но способ быстрый поиск (опять же с использованием ключевого слова in), если элемент содержится. Кажется, это все, что вам нужно знать.

На моей машине, тайминги являются:

using list 
1421499228.707602 
1421499232.764034 
using set 
1421499232.7644095 
1421499232.785762 

Так она занимает около 4 секунд со списком и 2 сотых секунды с набором.

Answer 4

Для этого вам понадобится структура данных Bag. В элементах структуры данных Bag нет порядка, но он предназначен для быстрого поиска элемента в Bag.Это временная сложность O(1). Таким образом, для N слов в статье общая сложность оказывается O(N). Это лучшее, что вы можете добиться в этом случае. Java Set является примером реализации Bag на Java.