cấu trúc dữ liệu hiệu quả nhất cho danh sách chuỗi chỉ đọc (khoảng 100.000) với tìm kiếm tiền tố nhanh

Question

Tôi đang viết một ứng dụng cần đọc danh sách chuỗi từ tệp, lưu chúng trong cấu trúc dữ liệu và sau đó tra cứu các chuỗi đó bằng các tiền tố. Danh sách các chuỗi chỉ đơn giản là một danh sách các từ trong một ngôn ngữ nhất định. Ví dụ, nếu chức năng tìm kiếm được "stup" như một tham số, nó sẽ trả về ["stupid", "stupidity", "stupor" ...]. Nó sẽ làm như vậy trong thời gian O (log (n) * m), trong đó n là kích thước của cấu trúc dữ liệu và m là số lượng kết quả và nên càng nhanh càng tốt. Mức tiêu thụ bộ nhớ không phải là một vấn đề lớn ngay bây giờ. Tôi đang viết này trong python, vì vậy nó sẽ là tuyệt vời nếu bạn có thể chỉ cho tôi một cấu trúc dữ liệu phù hợp (tốt hơn) được thực hiện trong c với wrappers python.

Answer 1

Bạn muốn có một trie.

http://en.wikipedia.org/wiki/Trie

Tôi đã sử dụng chúng trong các chương trình Scrabble và Boggle. Chúng hoàn hảo cho trường hợp sử dụng mà bạn mô tả (tra cứu tiền tố nhanh).

Dưới đây là một số mã mẫu để xây dựng một trie bằng Python. Đây là từ một chương trình Boggle mà tôi đã đánh với nhau vài tháng trước. Phần còn lại là một bài tập cho người đọc. Nhưng đối với tiền tố kiểm tra về cơ bản bạn cần một phương thức bắt đầu tại nút gốc (biến words), theo các chữ cái tiền tố cho các nút con liên tiếp và trả về Đúng nếu đường dẫn đó được tìm thấy và sai khác.

class Node(object): 
    def __init__(self, letter='', final=False): 
     self.letter = letter 
     self.final = final 
     self.children = {} 
    def __contains__(self, letter): 
     return letter in self.children 
    def get(self, letter): 
     return self.children[letter] 
    def add(self, letters, n=-1, index=0): 
     if n < 0: n = len(letters) 
     if index >= n: return 
     letter = letters[index] 
     if letter in self.children: 
      child = self.children[letter] 
     else: 
      child = Node(letter, index==n-1) 
      self.children[letter] = child 
     child.add(letters, n, index+1) 

def load_dictionary(path): 
    result = Node() 
    for line in open(path, 'r'): 
     word = line.strip().lower() 
     result.add(word) 
    return result 

words = load_dictionary('dictionary.txt') 

Answer 2

trie (or prefix tree) âm thanh ngay lên hẻm của bạn. Nó có thể thực hiện tìm kiếm trên một chuỗi tiền tố có chiều dài m trong O (m) tôi tin.

Answer 3

mảng chuỗi.

tìm kiếm sau đó nhị phân thông qua nó để tìm kiếm trận đấu đầu tiên sau đó bước từng người một qua nó cho tất cả các trận đấu tiếp theo

danh sách

(i ban đầu đã liên kết ở đây quá ... nhưng tất nhiên điều này không có ngẫu nhiên truy cập vì vậy đây là 'bs' (mà có lẽ giải thích lý do tại sao tôi đã downvoted) tìm kiếm nhị phân của tôi vẫn là con đường nhanh nhất để đi mặc dù

Answer 4

Triển khai một số Python của tries:.

• http://jtauber.com/2005/02/trie.py
• http://www.koders.com/python/fid7B6BC1651A9E8BBA547552FE3F039479A4DECC45.aspx
• http://filoxus.blogspot.com/2007/11/trie-in-python.html