Tối ưu hóa một thuật toán tìm kiếm đơn giản

Question

Tôi đã chơi một chút với một công cụ tìm kiếm đơn giản, khá đơn giản và giờ đây tôi đang có một số mã phân loại phù hợp.

Đó là không phải là rất xinh đẹp, nhưng tôi không phải là rất tốt khi nói đến các thuật toán thông minh, vì vậy tôi đã hy vọng tôi có thể nhận được một số lời khuyên :)

Về cơ bản, tôi muốn mỗi kết quả tìm kiếm để có được chấm điểm dựa trên bao nhiêu từ khớp với tiêu chí tìm kiếm. 3 điểm cho mỗi từ chính xác và một điểm cho trận đấu phần

Ví dụ, nếu tôi tìm kiếm "mùa đông tuyết", đây sẽ là kết quả:

• mùa đôngtuyết => 6 điểm
• mùa đôngtuyết ing => 4 điểm
• mùa đông đất tuyết => 4 điểm
• mùa đông mặt trời => 3 điểm
• mùa đông đất tuyết ing => 2 điểm

Dưới đây là các mã:

String[] resultWords = result.split(" "); 
String[] searchWords = searchStr.split(" "); 
int score = 0; 
for (String resultWord : resultWords) { 
    for (String searchWord : searchWords) { 
     if (resultWord.equalsIgnoreCase(searchWord)) 
      score += 3; 
     else if (resultWord.toLowerCase().contains(searchWord.toLowerCase())) 
      score++; 
    } 
} 

Answer 1

Mã của bạn có vẻ ổn với tôi. Tôi đề xuất các thay đổi nhỏ:

Vì bạn đang trải qua tất cả các kết hợp có thể, bạn có thể nhận được toLowerCase() lưng của bạn khi bắt đầu.

Ngoài ra, nếu kết hợp chính xác đã xảy ra, bạn không cần phải thực hiện một số khác equals.

result = result.toLowerCase(); 
    searchStr = searchStr.toLowerCase(); 

    String[] resultWords = result.split(" "); 
    String[] searchWords = searchStr.split(" "); 
    int score = 0; 
    for (String resultWord : resultWords) { 
     boolean exactMatch = false; 
     for (String searchWord : searchWords) { 
      if (!exactMatch && resultWord.equals(searchWord)) { 
       exactMatch = true; 
       score += 3; 
      } else if (resultWord.contains(searchWord)) 
       score++; 
     } 
    } 

Tất nhiên, đây là cấp độ rất cơ bản.Nếu bạn đang thực sự quan tâm đến lĩnh vực này của khoa học máy tính và muốn tìm hiểu thêm về triển khai công cụ tìm kiếm bắt đầu với những điều khoản này:

• Natural Language Processing
• Information retrieval
• Text mining

Answer 2

Tối ưu hóa cơ bản có thể được thực hiện bằng cách xử lý trước cơ sở dữ liệu của bạn: không chia các mục thành từng từ.

Xây dựng danh sách từ (thích băm hoặc cây nhị phân để tăng tốc tìm kiếm trong danh sách) cho mỗi mục nhập trong khi thêm nó vào DB, xóa tất cả các từ quá ngắn, chữ thường và lưu trữ dữ liệu này để sử dụng thêm.

Thực hiện các thao tác tương tự với chuỗi tìm kiếm khi bắt đầu tìm kiếm (tách, chữ thường, dọn dẹp) và sử dụng danh sách từ này để so sánh với mọi danh sách từ nhập.

Answer 3

• stemming
• cho từ viết tắt của chữ viết hoa là quan trọng, nghĩa là SUN; bất kỳ từ nào phù hợp với cả nội dung và trường hợp phải có trọng số lớn hơn 3 điểm (5 hoặc 7)?
• sử dụng strategy design pattern

Ví dụ, hãy xem xét mô hình này điểm ngây thơ:

interface ScoreModel { 
    int startingScore(); 
    int partialMatch(); 
    int exactMatch(); 
} 

...

int search(String result, String searchStr, ScoreModel model) { 
    String[] resultWords = result.split(" "); 
    String[] searchWords = searchStr.split(" "); 
    int score = model.startingScore(); 

    for (String resultWord : resultWords) { 
     for (String searchWord : searchWords) { 
      if (resultWord.equalsIgnoreCase(searchWord)) { 
       score += model.exactMatch(); 
      } else if (resultWord.toLowerCase().contains(searchWord.toLowerCase())) { 
       score += model.partialMatch(); 
      } 
     } 
    } 

    return score; 
} 

Answer 4

1) Bạn có thể sắp xếp searchWords đầu tiên. Bạn có thể thoát ra khỏi vòng lặp khi từ kết quả của bạn theo thứ tự bảng chữ cái sau từ tìm kiếm hiện tại của bạn.

2) Thậm chí tốt hơn, sắp xếp cả hai, sau đó đi bộ dọc theo cả hai danh sách cùng lúc để tìm vị trí bất kỳ kết quả trùng khớp nào xảy ra.

Answer 5

Bạn có thể sử dụng cụm từ thông dụng để tìm mẫu và độ dài của mẫu phù hợp (để phân loại/ghi điểm sau).