Python - 高速ファイル検索

Question

私は、ファイル数が（50-100万文字）のファイルを持っています。私が必要とするのは、これらの行を特定のクエリで高速に検索することです。今、私のコードは次のようになります。

def similarity(haystack, needle): 
    words = re.findall(r'\w+', haystack.lower()) # replacing by split with separators reduces time by about 4 seconds 

    for word in words: 
     if word == needle: 
      return 10 

    for word in words: 
     if word.startswith(needle): 
      return 10 ** (len(needle)/len(word)) 

    if needle in haystack: 
     return 1 

    return 0 

def search(text): 
    text = text.lower() 
    lines = [(similarity(x, text), x) for x in lines] 
    return [x[1] for x in sorted(lines, reverse = True)[:15]] 

それは（ほとんどすべての時間がsimilarity()機能である）私のPCでファイルの例では約15秒を実行し、私はそれが数秒で、ほとんどすぐに実行したいです。これはどうすればできますか？

インデックス作成は役に立ちますが、その可能な構造については考えていないと思います。可能であれば、検索を「より曖昧」にしたいと思います。 Nグラムやそれに類するもので。しかし、主な関心は今やスピードです。

UPD：

同じlinesを複数回通って検索されます。

needleは常に1語です。

「More fuzzy」は、needleが誤って入力されていても、行が見つかることを意味します。それは、 "S" と "t" があることははっきりしない今のよう10 ** (len(t)/len(word))

あなたは、より良い変数名が必要になります。

Answer 1

1. この行は何もしません。 1文字の変数名は、数学とループ変数としてのみ使用できます。あなたが探しているものは何ですか、あなたが探しているものは何ですか？現在使用されているような機能は私にはあまり意味がありません。

2. あなたが検索したものの最初の一致のみに一致するので、場合によっては分割が無意味なので、最後に分割を移動することもできますが、実際に何を検索しているかによって異なります。 2）。

更新：実際にこの中から最高のパフォーマンスを得るには、プロファイルを作成し、テストし、プロファイルしてテストする必要があります。しかし、私は最初のスタートとしてこれを提案したい：

def similarity(haystack, needle): 

    if needle not in haystack: 
     return 0 

    words = haystack.lower().split() 

    if needle in words: 
     return 10 

    for word in words: 
     if word.startswith(needle): 
      return 10 ** (len(needle)/len(word)) 

    return 1 

Answer 2

あなたは文字列を検索するには、同じファイルを使用しているので。永続的な辞書を使用すると、検索のスピードアップを図ることができます。

ロジックを考慮してください。あなたはこれを使うことができます。

import shelve 
import os 

PERSISTENT_DICT_FILENAME = "my_persistent_dict" 

def create_a_persitant_dict(haystack_filename): 
    pd = shelve.open(PERSISTENT_DICT_FILENAME) 
    f = open(haystack_filename) 
    for filename in f: 
     filename_len = len(filename) 
     filename = filename.lower() 
     for i in range(1,filename_len): 
      partial_filename = filename[:i] 
       calculation = 10 ** ((len(partial_filename)*1.0)/filename_len) 
       if pd.has_key(partial_filename): 
         if calculation > pd[partial_filename]: 
          pd[partial_filename] = calculation 
       else: 
        pd[partial_filename] = calculation 

    pd.close() 

def search_string(needle): 
    needle = needle.lower() 
    pd = shelve.open(PERSISTENT_DICT_FILENAME) 
    if pd.has_key(needle): 
     return_val = pd[needle] 
    else: 
     return_val = 0 
    pd.close() 
    return return_val 

if __name__ == "__main__": 
    #create_a_persitant_dict("a_large_file.txt") 
    needle = raw_input("Enter the string to search") 
    print search_string(needle) 

説明：

create_a_persitant_dict(haystack_filename) 

大きなファイルを読み込む永続的な辞書を作成します。キーはファイル内の文字列です（例：ファイル内の行が "World.txt"の場合、キーは "w"、 "wo"、 "wor"、worl ...などとなります）値は各キーの計算値（10 **など）です

これは単なる高価な操作ですが、検索を高速化することが目的です。

search_string(needle) 

この関数は、永続的辞書の文字列を検索し、ロジックに基づいて計算を行います。それは毎回繰り返すよりも速くなります。