Tìm mục từ điển có trận đấu một xâu chìa khóa

Question

Tôi đã một cuốn từ điển lớn được xây dựng như sau:

programs['New York'] = 'some values...' 
programs['Port Authority of New York'] = 'some values...' 
programs['New York City'] = 'some values...' 
... 

Làm thế nào tôi có thể trả lại tất cả programs mà quan trọng đề cập đến "new york" (case insensitive) - mà trong ví dụ trên , sẽ trả lại tất cả ba mục.

CHỈNH SỬA: Từ điển khá lớn và dự kiến ​​sẽ lớn hơn theo thời gian.

Answer 1

[value for key, value in programs.items() if 'new york' in key.lower()] 

Answer 2

Một iteritems và một biểu thức máy phát điện sẽ làm điều này:

d={'New York':'some values', 
    'Port Authority of New York':'some more values', 
    'New York City':'lots more values'} 

print list(v for k,v in d.iteritems() if 'new york' in k.lower())  

Output:

['lots more values', 'some more values', 'some values'] 

Answer 3

Bạn có thể tạo ra tất cả các chuỗi con trước thời hạn, và bản đồ chúng phím tương ứng của họ.

#generates all substrings of s. 
def genSubstrings(s): 
    #yield all substrings that contain the first character of the string 
    for i in range(1, len(s)+1): 
     yield s[:i] 
    #yield all substrings that don't contain the first character 
    if len(s) > 1: 
     for j in genSubstrings(s[1:]): 
      yield j 

keys = ["New York", "Port Authority of New York", "New York City"] 
substrings = {} 
for key in keys: 
    for substring in genSubstrings(key): 
     if substring not in substrings: 
      substrings[substring] = [] 
     substrings[substring].append(key) 

Sau đó, bạn có thể truy vấn substrings để có được các phím có chứa chuỗi con rằng:

>>>substrings["New York"] 
['New York', 'Port Authority of New York', 'New York City'] 
>>> substrings["of New York"] 
['Port Authority of New York'] 

Ưu điểm:

• nhận được chìa khóa của chuỗi là nhanh như truy cập vào một từ điển.

Nhược điểm:

• Tạo substrings gánh chịu một chi phí một lần vào đầu chương trình của bạn, dành thời gian tỉ lệ với số phím trong programs.
• substrings sẽ tăng xấp xỉ tuyến tính với số lượng khóa trong programs, tăng mức sử dụng bộ nhớ của tập lệnh của bạn.
• genSubstrings có hiệu suất O (n^2) liên quan đến kích thước khóa của bạn. Ví dụ, "Port Authority của New York" tạo ra 351 chất nền.

Answer 4

Bạn nên sử dụng phương pháp bạo lực được cung cấp bởi mensi cho đến khi nó tỏ ra quá chậm.

Đây là nội dung trùng lặp dữ liệu để tìm kiếm nhanh hơn. Nó chỉ hoạt động nếu tìm kiếm của bạn chỉ dành cho toàn bộ từ - nghĩa là bạn sẽ không bao giờ cần phải đối sánh với "Bánh mì tròn ngon nhất ở New York" vì "york" và "yorks" là các từ khác nhau.

words = {} 
for key in programs.keys(): 
    for w in key.split(): 
     w = w.lower() 
     if w not in words: 
      words[w] = set() 
     words[w].add(key) 


def lookup(search_string, words, programs): 
    result_keys = None 
    for w in search_string.split(): 
     w = w.lower() 
     if w not in words: 
      return [] 
     result_keys = words[w] if result_keys is None else result_keys.intersection(words[w]) 
    return [programs[k] for k in result_keys] 

Nếu những lời phải theo thứ tự (ví dụ: "New York" nên không phù hợp), bạn có thể áp dụng phương pháp brute-force vào danh sách ngắn của result_keys.

Answer 5

Điều này thường được gọi là từ điển thoải mái và có thể được triển khai hiệu quả bằng cách sử dụng cây hậu tố.

Bộ nhớ được sử dụng theo phương pháp này là tuyến tính trên các khóa, tối ưu và thời gian tìm kiếm tuyến tính trên độ dài chuỗi con bạn đang tìm kiếm, cũng tối ưu.

Tôi đã tìm thấy thư viện này trong python thực hiện việc này.

https://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/