Cách hiệu quả nhất để lập chỉ mục các từ trong tài liệu?

Question

Điều này xuất hiện trong một câu hỏi khác, nhưng tôi nghĩ tốt nhất nên hỏi câu hỏi này là một câu hỏi riêng. Cung cấp danh sách câu lớn (thứ tự 100 nghìn):

[ 
"This is sentence 1 as an example", 
"This is sentence 1 as another example", 
"This is sentence 2", 
"This is sentence 3 as another example ", 
"This is sentence 4" 
] 

cách tốt nhất để mã hóa chức năng sau là gì?

def GetSentences(word1, word2, position): 
    return "" 

nơi cho hai chữ, word1, word2 và một vị trí position, hàm sẽ trả về danh sách của tất cả các câu thoả mãn ràng buộc. Ví dụ:

GetSentences("sentence", "another", 3) 

nên trở lại câu 1 và 3 như chỉ số của câu. Cách tiếp cận hiện tại của tôi là sử dụng một từ điển như thế này:

Index = defaultdict(lambda: defaultdict(lambda: defaultdict(lambda: []))) 

for sentenceIndex, sentence in enumerate(sentences): 
    words = sentence.split() 
    for index, word in enumerate(words): 
     for i, word2 in enumerate(words[index:): 
      Index[word][word2][i+1].append(sentenceIndex) 

Nhưng điều này nhanh chóng thổi mọi thứ ra khỏi bộ dữ liệu có kích thước khoảng 130 MB khi RAM 48 GB của tôi cạn hết chưa tới 5 phút. Tôi bằng cách nào đó có được một cảm giác đây là một vấn đề phổ biến nhưng không thể tìm thấy bất kỳ tài liệu tham khảo về cách giải quyết này hiệu quả. Bất kỳ đề xuất về cách tiếp cận này?

Answer 1

Sử dụng cơ sở dữ liệu để lưu trữ giá trị.

1. Đầu tiên thêm tất cả các câu vào một bảng (chúng phải có ID). Bạn có thể gọi nó là ví dụ. sentences.
2. Thứ hai, tạo bảng có các từ chứa trong tất cả các câu (ví dụ: words, cung cấp cho mỗi từ một ID), lưu kết nối giữa các bản ghi bảng câu và từ bảng trong bảng riêng biệt. sentences_words, cần có hai cột, tốt nhất là word_id và sentence_id).

3. Khi tìm kiếm câu có chứa tất cả các từ đã đề cập, công việc của bạn sẽ được đơn giản hóa:

   1. Bạn nên đầu tiên tìm hồ sơ từ words bảng, nơi lời là chính xác những người bạn tìm kiếm. Truy vấn có thể trông như thế này:

      SELECT `id` FROM `words` WHERE `word` IN ('word1', 'word2', 'word3'); 
      

   2. Thứ hai, bạn nên tìm sentence_id giá trị từ bảng sentences mà đòi hỏi word_id giá trị (tương ứng với những lời từ words bảng). Các truy vấn ban đầu có thể trông như thế này:

      SELECT `sentence_id`, `word_id` FROM `sentences_words` 
      WHERE `word_id` IN ([here goes list of words' ids]); 
      

      mà có thể được đơn giản hóa như sau:

      SELECT `sentence_id`, `word_id` FROM `sentences_words` 
      WHERE `word_id` IN (
          SELECT `id` FROM `words` WHERE `word` IN ('word1', 'word2', 'word3') 
      ); 
      

   3. Lọc kết quả trong vòng Python trở lại chỉ sentence_id giá trị mà có tất cả các yêu cầu word_id ID bạn nhu cầu.

này về cơ bản là một giải pháp dựa trên lưu trữ lượng lớn dữ liệu trong các hình thức đó là phù hợp nhất cho điều này - cơ sở dữ liệu.

EDIT:

1. Nếu bạn sẽ chỉ tìm kiếm hai từ, bạn có thể làm nhiều hơn (hầu như tất cả mọi thứ) đứng về phía DBMS'.
2. Bạn cần lưu trữ vị trí của từ trong cột thứ ba của sentences_words bảng (cho phép gọi nó là position) và khi tìm kiếm các từ thích hợp, bạn nên tính toán sự khác biệt của giá trị này được liên kết với cả hai từ.

Answer 2

Đây là cách tôi đã thực hiện nó bằng Python. Mặc dù giả định điều này cần phải được thực hiện nhiều lần, một DBMS là công cụ thích hợp cho công việc. Tuy nhiên điều này dường như làm việc khá tốt cho tôi với một triệu hàng.

sentences = [ 
    "This is sentence 1 as an example", 
    "This is sentence 1 as another example", 
    "This is sentence 2", 
    "This is sentence 3 as another example ", 
    "This is sentence 4" 
    ] 

sentences = sentences * 200 * 1000 

sentencesProcessed = [] 

def preprocess(): 
    global sentences 
    global sentencesProcessed 
    # may want to do a regex split on whitespace 
    sentencesProcessed = [sentence.split(" ") for sentence in sentences] 

    # can deallocate sentences now 
    sentences = None 


def GetSentences(word1, word2, position): 
    results = [] 
    for sentenceIndex, sentence in enumerate(sentencesProcessed): 
     for wordIndex, word in enumerate(sentence[:-position]): 
      if word == word1 and sentence[wordIndex + position] == word2: 
       results.append(sentenceIndex) 
    return results 

def main(): 
    preprocess() 
    results = GetSentences("sentence", "another", 3) 
    print "Got", len(results), "results" 

if __name__ == "__main__": 
    main()