Java: cách tìm chuỗi có thể xảy ra nhất trong danh sách chuỗi?

Question

Tôi có một danh sách các chuỗi trong Java có chứa tên của một người có cách viết khác nhau (không hoàn toàn khác). Ví dụ, John có thể được viết như Jon, Jawn, Jaun, vv Làm thế nào tôi nên lấy chuỗi thích hợp nhất trong danh sách này. Nếu bất cứ ai có thể đề xuất một phương pháp làm thế nào để sử dụng Soundex trong trường hợp này, nó sẽ được giúp đỡ rất nhiều.

Answer 1

Bạn đã sử dụng thuật toán approximate string matching, Có một số chiến lược để thực hiện việc này. Blur là một thực thi dựa trên Trie dựa trên Java đối xứng chuỗi gần đúng dựa trên khoảng cách từ Levenshtein. you can find the implementation at github here

Có một chiến lược khác để triển khai thuật toán kết hợp chuỗi gần đúng của người bạn trai. Here is the Java code for that

Cách tiếp cận thông thường để giải quyết vấn đề này bằng thuật toán này và khoảng cách từ Levenshtein là so sánh đầu vào với đầu ra có thể và chọn kết quả có khoảng cách nhỏ nhất đến đầu ra mong muốn.

Answer 2

Solr có thể thực hiện việc này, nếu bạn sử dụng phonetic filter factory trong khi lập chỉ mục văn bản.

Đó là đặc sản của solr để tìm kiếm. Và tìm kiếm các từ tương tự. Tuy nhiên nếu bạn chỉ muốn điều này, và không muốn các tính năng khác được cung cấp bởi solr, sau đó bạn có thể sử dụng nguồn có sẵn here.

Answer 3

Có một file jar cho phù hợp với chuỗi gần đúng ..

đi qua liên kết và tải frej.jar

http://sourceforge.net/projects/frej/files/

có một phương pháp bên trong file jar này

Fuzzy.equals("jon","john"); 

nó sẽ trả về true trong loại chuỗi gần đúng này.

Answer 4

Có rất nhiều lý thuyết và phương pháp để ước tính trận đấu của 2 chuỗi

Đưa ra một kết quả đúng/sai cùn thôi, mặc dù "jon" thực sự không bằng "john", nó gần nhưng doesn 't phù hợp

một công việc học tập lớn thực hiện khá một vài phương pháp ước lượng được gọi là 'SecondString.jar' - site link

phương pháp triển khai Phần lớn đưa ra một số điểm đến trận đấu, tỷ số này phụ thuộc vào phương pháp sử dụng

Ví dụ: Cho phép xác định "Chỉnh sửa khoảng cách" là số lượng thay đổi char cần thiết trong str1 để đến str2 trong trường hợp này "jon" -> "john" yêu cầu thêm 1 char một cách tự nhiên cho phương pháp này là tốt hơn

Answer 5

Bài viết này cung cấp giải thích chi tiết và mã hoàn chỉnh về việc thực hiện Java dựa trên Trie đối sánh chuỗi gần đúng: Fast and Easy Levenshtein distance using a Trie.

Chức năng tìm kiếm trả về một danh sách tất cả các từ mà có ít hơn cho

khoảng cách tối đa từ chữ mục tiêu

def tìm kiếm (word, maxCost):

# build first row 
currentRow = range(len(word) + 1) 

results = [] 

# recursively search each branch of the trie 
for letter in trie.children: 
    searchRecursive(trie.children[letter], letter, word, currentRow, 
     results, maxCost) 

return results 

đệ quy này helper được sử dụng bởi hàm tìm kiếm ở trên. Nó giả định rằng

previousRow đã được điền sẵn.

def searchRecursive (nút, lá thư, văn bản, previousRow, kết quả, maxCost):

columns = len(word) + 1 
currentRow = [ previousRow[0] + 1 ] 

# Build one row for the letter, with a column for each letter in the target 
# word, plus one for the empty string at column 0 
for column in xrange(1, columns): 

    insertCost = currentRow[column - 1] + 1 
    deleteCost = previousRow[column] + 1 

    if word[column - 1] != letter: 
     replaceCost = previousRow[ column - 1 ] + 1 
    else:     
     replaceCost = previousRow[ column - 1 ] 

    currentRow.append(min(insertCost, deleteCost, replaceCost)) 

# if the last entry in the row indicates the optimal cost is less than the 
# maximum cost, and there is a word in this trie node, then add it. 
if currentRow[-1] <= maxCost and node.word != None: 
    results.append((node.word, currentRow[-1])) 

# if any entries in the row are less than the maximum cost, then 
# recursively search each branch of the trie 
if min(currentRow) <= maxCost: 
    for letter in node.children: 
     searchRecursive(node.children[letter], letter, word, currentRow, 
      results, maxCost)