Быстрый способ поиска строки в большом текстовом файле с помощью Python

1

Что моя текущая ситуация:

  • У меня есть текстовый файл размером 2,5 МБ со строками размером 250 тыс., отсортированный по алфавиту
  • Каждая строка уникальна.
  • Мне не нужно изменять записи в текстовом файле: после загрузки текстового файла он никогда не редактируется
  • Текстовый файл загружается при запуске, а затем мне просто нужно искать строки через него

Последняя проблема - проблема. На самом деле мне нужно найти полное соответствие AND для частичного совпадения строки. Алгоритм, который я написал, просто включал использование регулярных выражений в сочетании с некоторыми попытками сделать процесс быстрее: например, я жестко закодировал в свои script индексы словаря, который идентифицировал сингулярные буквы алфавита, а затем разделил большой текстовый файл fictionary в 26 меньших словарях. Это было совершенно бесполезно, script все еще невероятно медленный. Снимая некоторые сообщения здесь, я был убежден попробовать mmap: но было бесполезно находить все частичные совпадения, учитывая регулярное выражение. В конце концов я пришел к выводу, что trie может решить мою проблему, хотя я почти не знаю, что это такое. Должен ли я пойти с попытками? Если да, то как мне перейти к созданию trie в python? Является ли marisa-trie модулем хорошим? Спасибо всем

EDIT: "Частичное совпадение", я имею в виду, что у меня есть префикс строки. Мне не нужны матчи в конце или посередине, только в начале.

  • 0
    Пожалуйста, более подробно расскажу о том, что вы подразумеваете под частичным совпадением.
  • 0
    Да, является ли частичное совпадение префиксом каждой строки или содержит подстроку каждой строки? Построение дерева не поможет, если совпадения должны быть подстроками.
Показать ещё 2 комментария
Теги:
trie

6 ответов

5
Лучший ответ

Самое простое и быстрое решение:

#!/usr/bin/env python

d = {}

# open your file here, i'm using /etc/hosts as an example...
f = open("/etc/hosts","r")
for line in f:
    line = line.rstrip()
    l = len(line)+1
    for i in xrange(1,l):
        d[line[:i]] = True
f.close()


while True:
    w = raw_input('> ')
    if not w:
        break

    if w in d:
        print "match found", w

Вот несколько более сложный, но эффективный с точки зрения памяти:

#!/usr/bin/env python

d = []

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x:
            hi = mid
        else:
            return mid
    return -1


f = open("/etc/hosts","r")
for line in f:
    line=line.rstrip()
    l = len(line)+1
    for i in xrange(1,l):
        x = hash(line[:i])
        d.append(x)
f.close()

d.sort()

while True:
    w = raw_input('> ')
    if not w:
        break

    if binary_search(d, hash(w)) != -1:
        print "match found", w
Поделиться
  • 0
    Большое спасибо! Я не мог выбрать использование словаря, потому что мне нужно было отсортировать строки в алфавитном порядке - что невозможно с помощью dict. Я попробую ваше последнее решение
  • 0
    Вместо dict вы можете попробовать использовать модуль OrderedDict. Это может помочь в первом решении тоже. :)
2

Так как файл уже отсортирован и прочитан, вы можете использовать его для двоичного поиска, не прибегая к каким-либо причудливым структурам данных. Python имеет встроенную функцию двоичного поиска, bisect.bisect_left`.

Поделиться
1

Используйте trie.

#dictionary is a list of words
def parse_dictionary(dictionary):
    dictionary_trie = {}
    for word in dictionary:
        tmp_trie = dictionary_trie
        for letter in word:
            if letter not in tmp_trie:
                tmp_trie[letter] = {}
            if 'words' not in tmp_trie[letter]:
                tmp_trie[letter]['words'] = []

            tmp_trie[letter]['words'].append(word)
            tmp_trie = tmp_trie[letter]
    return dictionary_trie

def matches(substring, trie):
    d = trie
    for letter in substring:
        try:
            d = d[letter]
        except KeyError:
            return []
    return d['words']

Пример использования:

>>> import pprint
>>> dictionary = ['test', 'testing', 'hello', 'world', 'hai']
>>> trie = parse_dictionary(dictionary)
>>> pprint.pprint(trie)
{'h': {'a': {'i': {'words': ['hai']}, 'words': ['hai']},
       'e': {'l': {'l': {'o': {'words': ['hello']}, 'words': ['hello']},
                   'words': ['hello']},
             'words': ['hello']},
       'words': ['hello', 'hai']},
 't': {'e': {'s': {'t': {'i': {'n': {'g': {'words': ['testing']},
                                     'words': ['testing']},
                               'words': ['testing']},
                         'words': ['test', 'testing']},
                   'words': ['test', 'testing']},
             'words': ['test', 'testing']},
       'words': ['test', 'testing']},
 'w': {'o': {'r': {'l': {'d': {'words': ['world']}, 'words': ['world']},
                   'words': ['world']},
             'words': ['world']},
       'words': ['world']}}
>>> matches('h', trie)
['hello', 'hai']
>>> matches('he', trie)
['hello']
>>> matches('asd', trie)
[]
>>> matches('test', trie)
['test', 'testing']
>>>
Поделиться
0

Вы можете создать список, чтобы каждая строка была одним из элементов списка и выполняла двоичный поиск.

Поделиться
  • 0
    @nhahtdh, вопрос, в частности, гласит, что текст, который нужно найти, является префиксом, то есть в начале строки.
0

Итак, чтобы объяснить arainchi очень хороший ответ, сделайте словарь с записью для каждой строки в вашем файле. Затем вы можете сопоставить свою строку поиска с именами этих записей. Словари действительно удобны для такого поиска.

Поделиться
0

Использование trie по-прежнему требует, чтобы вы построили trie, который является O (n), чтобы итерировать весь файл. Использование сортировки сделает его O (log_2 n). Таким образом, это более быстрое решение будет использовать двоичный поиск (см. Ниже).

Это решение по-прежнему требует, чтобы вы прочитали весь файл. В еще более быстром решении вы можете предварительно обработать файл и выровнять все строки, чтобы они были одинаковой длины (или создавали какую-либо структуру индекса в файле, чтобы сделать поиск середины списка выполнимым) - - тогда поиск середины файла приведет вас к середине списка. Решение "еще быстрее", вероятно, понадобится только для действительно большого файла (гигабайт или сотни мегабайт). Вы бы объединили это с бинарным поиском.

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

Затем, в этот момент, вы, вероятно, приближаетесь к реализации дерева b или дерева b +, чтобы сделать индексирование эффективным. Таким образом, вы можете использовать библиотеку b-tree.

Что-то вроде этого:

import bisect

entries = ["a", "b", "c", "cc", "cd", "ce", "d", "e", "f" ]

def find_matches(ls, m):

    x = len(ls) / 2
    match_index = -1

    index = bisect.bisect_left(ls, m)
    matches = []

    while ls[index].startswith(m):
        matches.append(ls[index])
        index += 1

    return matches

print find_matches(entries, "c")

Вывод:

>>> ['c', 'cc', 'cd', 'ce']
Поделиться

Ещё вопросы

Сообщество Overcoder
Наверх
Меню