Kiểm tra chuỗi con/chuỗi con gần đúng tồn tại trong một chuỗi dài hơn, bằng Python?

Question

Sử dụng các thuật toán như leveinstein (leveinstein hoặc difflib), rất dễ dàng để tìm các kết quả phù hợp.eg.

>>> import difflib 
>>> difflib.SequenceMatcher(None,"amazing","amaging").ratio() 
0.8571428571428571 

Có thể phát hiện các kết quả mờ bằng cách quyết định ngưỡng khi cần.

Yêu cầu hiện tại: Để tìm chuỗi con mờ dựa trên ngưỡng trong chuỗi lớn hơn.

ví dụ:

large_string = "thelargemanhatanproject is a great project in themanhattincity" 
query_string = "manhattan" 
#result = "manhatan","manhattin" and their indexes in large_string 

Một giải pháp brute force là để tạo ra tất cả các chuỗi con có chiều dài N-1 đến N + 1 (hoặc chiều dài phù hợp khác), trong đó N là chiều dài của QUERY_STRING, và sử dụng Levenstein trên từng cái một và xem ngưỡng.

Có giải pháp tốt hơn có sẵn trong python hay không, tốt nhất là mô-đun đi kèm trong python 2.7 hoặc mô-đun có sẵn bên ngoài.

CẬP NHẬT: Mô-đun regex Python hoạt động khá tốt, mặc dù nó chậm hơn một chút so với mô đun re sẵn có cho các hoạt động phụ. Đầu ra mong muốn là tốt và việc kiểm soát độ lớn của độ mờ có thể dễ dàng được xác định.

>>> import regex 
>>> input = "Monalisa was painted by Leonrdo da Vinchi" 
>>> regex.search(r'\b(leonardo){e<3}\s+(da)\s+(vinci){e<2}\b',input,flags=regex.IGNORECASE) 
<regex.Match object; span=(23, 41), match=' Leonrdo da Vinchi', fuzzy_counts=(0, 2, 1)> 

Answer 1

Thư viện regex mới sắp được thay thế bao gồm cả kết hợp mờ.

https://pypi.python.org/pypi/regex/

Cú pháp kết hợp mờ trông khá biểu cảm, nhưng điều này sẽ cung cấp cho bạn một trận đấu với một hoặc ít chèn/bổ sung/xóa.

import regex 
regex.match('(amazing){e<=1}', 'amaging') 

Answer 2

Cách sử dụng difflib.SequenceMatcher.get_matching_blocks?

>>> import difflib 
>>> large_string = "thelargemanhatanproject" 
>>> query_string = "manhattan" 
>>> s = difflib.SequenceMatcher(None, large_string, query_string) 
>>> sum(n for i,j,n in s.get_matching_blocks())/float(len(query_string)) 
0.8888888888888888 

>>> query_string = "banana" 
>>> s = difflib.SequenceMatcher(None, large_string, query_string) 
>>> sum(n for i,j,n in s.get_matching_blocks())/float(len(query_string)) 
0.6666666666666666 

---

CẬP NHẬT

import difflib 

def matches(large_string, query_string, threshold): 
    words = large_string.split() 
    for word in words: 
     s = difflib.SequenceMatcher(None, word, query_string) 
     match = ''.join(word[i:i+n] for i, j, n in s.get_matching_blocks() if n) 
     if len(match)/float(len(query_string)) >= threshold: 
      yield match 

large_string = "thelargemanhatanproject is a great project in themanhattincity" 
query_string = "manhattan" 
print list(matches(large_string, query_string, 0.8)) 

Trên đang in: ['manhatan', 'manhattn']

Answer 3

Gần đây tôi đã viết một thư viện liên kết cho Python: https://github.com/eseraygun/python-alignment

Sử dụng nó, bạn có thể thực hiện cả hai và sự sắp xếp địa phương với các chiến lược chấm điểm tùy ý trên bất kỳ chuỗi nào. Trên thực tế, trong trường hợp của bạn, bạn cần sắp xếp bán cục bộ khi bạn không quan tâm đến các chất nền của query_string. Tôi đã mô phỏng thuật toán bán cục bộ bằng cách sử dụng căn chỉnh cục bộ và một số chẩn đoán trong đoạn mã sau nhưng rất dễ mở rộng thư viện để thực hiện đúng.

Đây là mã ví dụ trong tệp README được sửa đổi cho trường hợp của bạn.

from alignment.sequence import Sequence, GAP_ELEMENT 
from alignment.vocabulary import Vocabulary 
from alignment.sequencealigner import SimpleScoring, LocalSequenceAligner 

large_string = "thelargemanhatanproject is a great project in themanhattincity" 
query_string = "manhattan" 

# Create sequences to be aligned. 
a = Sequence(large_string) 
b = Sequence(query_string) 

# Create a vocabulary and encode the sequences. 
v = Vocabulary() 
aEncoded = v.encodeSequence(a) 
bEncoded = v.encodeSequence(b) 

# Create a scoring and align the sequences using local aligner. 
scoring = SimpleScoring(1, -1) 
aligner = LocalSequenceAligner(scoring, -1, minScore=5) 
score, encodeds = aligner.align(aEncoded, bEncoded, backtrace=True) 

# Iterate over optimal alignments and print them. 
for encoded in encodeds: 
    alignment = v.decodeSequenceAlignment(encoded) 

    # Simulate a semi-local alignment. 
    if len(filter(lambda e: e != GAP_ELEMENT, alignment.second)) != len(b): 
     continue 
    if alignment.first[0] == GAP_ELEMENT or alignment.first[-1] == GAP_ELEMENT: 
     continue 
    if alignment.second[0] == GAP_ELEMENT or alignment.second[-1] == GAP_ELEMENT: 
     continue 

    print alignment 
    print 'Alignment score:', alignment.score 
    print 'Percent identity:', alignment.percentIdentity() 
    print 

Đầu ra cho minScore=5 như sau.

m a n h a - t a n 
m a n h a t t a n 
Alignment score: 7 
Percent identity: 88.8888888889 

m a n h a t t - i 
m a n h a t t a n 
Alignment score: 5 
Percent identity: 77.7777777778 

m a n h a t t i n 
m a n h a t t a n 
Alignment score: 7 
Percent identity: 88.8888888889 

Nếu bạn xóa đối số minScore, bạn sẽ chỉ nhận được kết quả phù hợp nhất.

m a n h a - t a n 
m a n h a t t a n 
Alignment score: 7 
Percent identity: 88.8888888889 

m a n h a t t i n 
m a n h a t t a n 
Alignment score: 7 
Percent identity: 88.8888888889 

Lưu ý rằng tất cả các thuật toán trong thư viện có O(n * m) thời gian phức tạp, n và m là độ dài của chuỗi.

Answer 4

tôi sử dụng fuzzywuzzy để trận đấu mờ dựa trên ngưỡng và fuzzysearch lời trích mờ từ trận đấu.

process.extractBests nhận truy vấn, danh sách các từ và điểm cắt và trả về danh sách các bộ so khớp và điểm số cao hơn điểm cắt.

find_near_matches lấy kết quả là process.extractBests và trả về chỉ mục bắt đầu và kết thúc của từ. Tôi sử dụng các chỉ số để xây dựng các từ và sử dụng từ được xây dựng để tìm chỉ mục trong chuỗi lớn. max_l_dist của find_near_matches là 'khoảng cách Levenshtein' phải được điều chỉnh cho phù hợp với nhu cầu.

from fuzzysearch import find_near_matches 
from fuzzywuzzy import process 

large_string = "thelargemanhatanproject is a great project in themanhattincity" 
query_string = "manhattan" 

def fuzzy_extract(qs, ls, threshold): 
    '''fuzzy matches 'qs' in 'ls' and returns list of 
    tuples of (word,index) 
    ''' 
    for word, _ in process.extractBests(qs, (ls,), score_cutoff=threshold): 
     print('word {}'.format(word)) 
     for match in find_near_matches(qs, word, max_l_dist=1): 
      match = word[match.start:match.end] 
      print('match {}'.format(match)) 
      index = ls.find(match) 
      yield (match, index) 

Kiểm tra;

print('query: {}\nstring: {}'.format(query_string, large_string)) 
for match,index in fuzzy_extract(query_string, large_string, 70): 
    print('match: {}\nindex: {}'.format(match, index)) 

query_string = "citi" 
print('query: {}\nstring: {}'.format(query_string, large_string)) 
for match,index in fuzzy_extract(query_string, large_string, 30): 
    print('match: {}\nindex: {}'.format(match, index)) 

query_string = "greet" 
print('query: {}\nstring: {}'.format(query_string, large_string)) 
for match,index in fuzzy_extract(query_string, large_string, 30): 
    print('match: {}\nindex: {}'.format(match, index)) 

Đầu ra;
truy vấn: manhattan
chuỗi: thelargemanhatanproject là một dự án lớn trong themanhattincity
trận đấu: manhatan
chỉ số: 8
trận đấu: manhattin
chỉ số: 49

truy vấn: Citi
chuỗi: thelargemanhatanproject là một dự án tuyệt vời trong themanhattincity
đối sánh: thành phố
chỉ số: 58

truy vấn: chào
chuỗi: thelargemanhatanproject là một dự án lớn trong themanhattincity
trận đấu: tuyệt vời
chỉ số: 29

Answer 5

Các cách tiếp cận trên là tốt, nhưng tôi cần phải tìm một cây kim nhỏ trong rất nhiều cỏ khô, và đã kết thúc tiếp cận nó như thế này:

from difflib import SequenceMatcher as SM 
from nltk.util import ngrams 
import codecs 

needle = "this is the string we want to find" 
hay = "text text lots of text and more and more this string is the one we wanted to find and here is some more and even more still" 

needle_length = len(needle.split()) 
max_sim_val = 0 
max_sim_string = u"" 

for ngram in ngrams(hay.split(), needle_length + int(.2*needle_length)): 
    hay_ngram = u" ".join(ngram) 
    similarity = SM(None, hay_ngram, needle).ratio() 
    if similarity > max_sim_val: 
     max_sim_val = similarity 
     max_sim_string = hay_ngram 

print max_sim_val, max_sim_string 

Sản lượng:

0.72972972973 this string is the one we wanted to find