Vấn đề tìm kiếm chuỗi khối lượng hiệu quả

Question

Vấn đề: Danh sách chuỗi tĩnh lớn được cung cấp. Một chuỗi mẫu bao gồm dữ liệu và các phần tử ký tự đại diện (* và?). Ý tưởng là trả về tất cả các chuỗi khớp với mẫu - đủ đơn giản.

Giải pháp hiện tại: Tôi hiện đang sử dụng cách tiếp cận tuyến tính để quét danh sách lớn và gộp từng mục nhập vào mẫu.

Câu hỏi của tôi: Có cấu trúc dữ liệu phù hợp nào để lưu trữ danh sách lớn vào mức phức tạp của tìm kiếm nhỏ hơn O (n) không?

Có lẽ giống như một số hậu tố-trie? Tôi cũng đã xem xét sử dụng bi-tri và gam trong một hashtable, nhưng logic cần thiết trong việc đánh giá một trận đấu dựa trên sự hợp nhất của danh sách các từ được trả về và mô hình là một cơn ác mộng, hơn nữa tôi không thuyết phục nó đúng tiếp cận.

Answer 1

Nếu bạn không quan tâm đến bộ nhớ và bạn có thể đủ khả năng xử lý danh sách, hãy tạo một mảng được sắp xếp theo mọi hậu tố, chỉ vào từ gốc, ví dụ, cho ['hello', 'world'], lưu trữ này:

[('d' , 'world'), 
('ello' , 'hello'), 
('hello', 'hello'), 
('ld' , 'world'), 
('llo' , 'hello'), 
('lo' , 'hello'), 
('o' , 'hello'), 
('orld' , 'world'), 
('rld' , 'world'), 
('world', 'world')] 

sử dụng mảng này để xây dựng bộ ứng cử viên trận đấu bằng các mẩu mô hình.

Ví dụ: nếu mẫu là *or*, hãy tìm kết quả ứng cử viên ('orld' , 'world') bằng cách sử dụng một băm nhị phân trên chuỗi con or, sau đó xác nhận kết quả phù hợp bằng cách sử dụng phương pháp globbing bình thường.

Nếu ký tự đại diện phức tạp hơn, ví dụ: h*o, tập hợp các ứng cử viên cho h và o và tìm giao điểm của chúng trước khi kết quả tuyến tính cuối cùng.

Answer 2

bạn có thể tạo một trie thông thường và thêm các cạnh ký tự đại diện. thì độ phức tạp của bạn sẽ là O (n) trong đó n là chiều dài của mẫu. Bạn sẽ phải thay thế số lần chạy của ** bằng * trong mẫu trước (cũng là thao tác O (n)).

Nếu danh sách các từ đã Tôi là một con bò thì Trie sẽ nhìn một chút như thế này:

 
    (I ($ [I]) 
    a (m ($ [am]) 
     n ($ [an]) 
     ? ($ [am an]) 
     * ($ [am an])) 
    o (x ($ [ox]) 
     ? ($ [ox]) 
     * ($ [ox])) 
    ? ($ [I] 
     m ($ [am]) 
     n ($ [an]) 
     x ($ [ox]) 
     ? ($ [am an ox]) 
     * ($ [I am an ox] 
     m ($ [am]) ...) 
    * ($ [I am an ox] 
     I ... 
    ... 

Và đây là một chương trình mẫu python:

 
import sys 

def addWord(root, word): 
    add(root, word, word, '') 

def add(root, word, tail, prev): 
    if tail == '': 
     addLeaf(root, word) 
    else: 
     head = tail[0] 
     tail2 = tail[1:] 
     add(addEdge(root, head), word, tail2, head) 
     add(addEdge(root, '?'), word, tail2, head) 
    if prev != '*': 
     for l in range(len(tail)+1): 
      add(addEdge(root, '*'), word, tail[l:], '*') 

def addEdge(root, char): 
    if not root.has_key(char): 
     root[char] = {} 
    return root[char] 

def addLeaf(root, word): 
    if not root.has_key('$'): 
     root['$'] = [] 
    leaf = root['$'] 
    if word not in leaf: 
     leaf.append(word) 

def findWord(root, pattern): 
    prev = '' 
    for p in pattern: 
     if p == '*' and prev == '*': 
      continue 
     prev = p 
     if not root.has_key(p): 
      return [] 
     root = root[p] 
    if not root.has_key('$'): 
     return [] 
    return root['$'] 

def run(): 
    print("Enter words, one per line terminate with a . on a line") 
    root = {} 
    while 1: 
     line = sys.stdin.readline()[:-1] 
     if line == '.': break 
     addWord(root, line) 
    print(repr(root)) 
    print("Now enter search patterns. Do not use multiple sequential '*'s") 
    while 1: 
     line = sys.stdin.readline()[:-1] 
     if line == '.': break 
     print(findWord(root, line)) 

run() 

Answer 3

Tôi đồng ý rằng một hậu tố trie là một ý tưởng tốt để thử, ngoại trừ kích thước tuyệt đối của bộ dữ liệu của bạn có thể làm cho nó xây dựng sử dụng hết thời gian như việc sử dụng của nó sẽ tiết kiệm. Họ tốt nhất nếu bạn phải truy vấn chúng nhiều lần để khấu hao chi phí xây dựng. Có lẽ một vài trăm truy vấn.

Cũng lưu ý rằng đây là lý do chính đáng cho tính song song. Cắt danh sách thành hai và đưa cho hai bộ vi xử lý khác nhau và thực hiện công việc của bạn nhanh gấp hai lần.

Answer 4

Bạn nói bạn hiện đang thực hiện tìm kiếm tuyến tính. Điều này có cung cấp cho bạn bất kỳ dữ liệu nào về các mẫu truy vấn được thực hiện thường xuyên nhất không? ví dụ. là blah* phổ biến hơn nhiều so với bl?h (mà tôi cho rằng đó là) trong số những người dùng hiện tại của bạn?

Với loại kiến ​​thức trước đó bạn có thể tập trung nỗ lực lập chỉ mục vào các trường hợp thường được sử dụng và đưa chúng xuống O (1), thay vì cố gắng giải quyết vấn đề khó khăn hơn, nhưng ít đáng giá hơn mỗi truy vấn có thể bằng nhau nhanh chóng.

Answer 5

Bạn có thể đạt được tốc độ đơn giản bằng cách giữ số lượng ký tự trong chuỗi của bạn. Một chuỗi không có b s hoặc một đơn b không bao giờ có thể khớp với truy vấn abba*, do đó không có điểm nào trong việc kiểm tra nó. Điều này làm việc tốt hơn nhiều trên toàn bộ từ, nếu dây của bạn được làm bằng những từ đó, vì có nhiều từ hơn ký tự; Ngoài ra, có rất nhiều thư viện có thể xây dựng các chỉ mục cho bạn. Mặt khác, nó rất giống với cách tiếp cận n-gram mà bạn đã đề cập.

Nếu bạn không sử dụng thư viện thực hiện cho bạn, bạn có thể tối ưu hóa truy vấn bằng cách tìm kiếm các ký tự không thường xuyên (hoặc từ hoặc n-gram) toàn cầu đầu tiên trong chỉ mục của bạn. Điều này cho phép bạn hủy nhiều chuỗi không phù hợp hơn ở phía trước.

Nói chung, tất cả các tăng tốc sẽ dựa trên ý tưởng loại bỏ những thứ không thể khớp. Điều gì và bao nhiêu để chỉ mục phụ thuộc vào dữ liệu của bạn. Ví dụ: nếu chiều dài mẫu điển hình gần với độ dài chuỗi, bạn có thể chỉ cần kiểm tra xem chuỗi có đủ dài để giữ mẫu không.

Answer 6

Có rất nhiều thuật toán tốt để tìm kiếm nhiều chuỗi. Google "Tìm kiếm chuỗi Navarro" và bạn sẽ thấy một phân tích tốt về các tùy chọn nhiều chuỗi. Một số thuật toán cực kỳ tốt cho các trường hợp "bình thường" (chuỗi tìm kiếm khá dài: Wu-Manber; các chuỗi tìm kiếm có các ký tự hiếm có trong văn bản cần tìm kiếm: song song Horspool). Aho-Corasick là một thuật toán đảm bảo một lượng nhỏ công việc giới hạn cho mỗi ký tự đầu vào, bất kể văn bản đầu vào được điều chỉnh như thế nào để tạo ra hành vi xấu nhất trong tìm kiếm. Đối với các chương trình như Snort, điều đó thực sự quan trọng, khi đối mặt với các cuộc tấn công từ chối dịch vụ. Nếu bạn quan tâm đến việc tìm kiếm Aho-Corasick thực sự hiệu quả có thể được thực hiện như thế nào, hãy xem ACISM - an Aho-Corasick Interleaved State Matrix.