Công cụ tìm từ có hình dạng nguệch ngoạc với các ký tự đại diện

Bạn không. Bảng cơ sở dữ liệu quan hệ không phải là cấu trúc dữ liệu phù hợp để giải quyết vấn đề này một cách hiệu quả như bạn cần.

Thay vào đó, những gì bạn làm là tạo trie cấu trúc dữ liệu ngoài từ điển (hoặc, nếu bạn thực sự giỏi, bạn xây dựng dawg - biểu đồ từ xoay chiều có hướng - là một loại trie được nén.)

Sau khi bạn có trie / dawg, việc kiểm tra mọi sẽ trở nên rất rẻ. từ trong từ điển so với một giá nhất định, vì bạn có thể "cắt bỏ" toàn bộ các nhánh khổng lồ của từ điển mà giá đó không thể khớp được.

Hãy xem một ví dụ nhỏ. Giả sử bạn có từ điển "OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS" Từ đó bạn xây dựng bộ ba này:(Các nút có $ là những nút được đánh dấu là "từ có thể kết thúc ở đây" .

           ^root^
           /  |  \
         O    P    S
         |    |   / \
         P$   O  O   T   
        / \   |  |   |
       T$  S$ T$ P$  O
       |      |  |   |
       S$     S$ S$  P$
                     |
                     S$

và bạn có giá "OPS" - bạn sẽ làm gì?

Đầu tiên bạn nói "tôi có thể xuống nhánh O được không?" Có, bạn có thể. Vì vậy, bây giờ vấn đề là khớp "PS" với nhánh O. Bạn có thể đi xuống kênh con P không? Đúng. Nó có một điểm đánh dấu cuối từ không? Vâng, vì vậy OP là một trận đấu. Bây giờ vấn đề là khớp "S" với nhánh OP. Bạn có thể đi xuống chi nhánh T được không? Không. Bạn có thể đi xuống chi nhánh S được không? Đúng. Bây giờ bạn có giá trống và bạn phải khớp nó với nhánh OPS. Nó có một điểm đánh dấu cuối từ không? Đúng! Vì vậy, OPS cũng phù hợp. Bây giờ sao lưu vào thư mục gốc.

Bạn có thể đi xuống nhánh P được không? Đúng. Bây giờ vấn đề là khớp OS với nhánh P. Đi xuống nhánh PO và khớp với S - không thành công. Quay lại thư mục gốc.

Và một lần nữa, bạn thấy điều này diễn ra như thế nào. Cuối cùng, chúng tôi đi xuống nhánh SOP và tìm thấy một từ cuối trên SOP, vì vậy "SOP" khớp với giá đỡ này. Chúng tôi không đi xuống chi nhánh ST vì chúng tôi không có T.

Chúng tôi đã thử mọi từ có thể có trong từ điển và phát hiện ra rằng OP, OPS và SOP đều khớp. Nhưng chúng tôi chưa bao giờ phải điều tra TÙY CHỌN, ĐIỂM, DỪNG hoặc DỪNG vì chúng tôi không có T.

Bạn thấy cách cấu trúc dữ liệu này làm cho nó rất hiệu quả? Một khi bạn đã xác định rằng bạn không có các chữ cái trên giá để tạo bắt đầu của một từ, bạn không phải điều tra bất kỳ từ điển bắt đầu với sự bắt đầu đó. Nếu bạn có PO nhưng không có T, bạn không phải điều tra POTSHERD hoặc POTATO hoặc POTASH hoặc POTLATCH hoặc POTABLE; tất cả những tìm kiếm tốn kém và không có kết quả đó sẽ biến mất rất nhanh.

Điều chỉnh hệ thống để đối phó với các ô "hoang dã" là khá đơn giản; Nếu bạn có OPS ?, thì chỉ cần chạy thuật toán tìm kiếm 26 lần, trên OPSA, OPSB, OPSC ... Nó phải đủ nhanh để làm điều đó 26 lần là rẻ (hoặc làm 26 x 26 lần nếu bạn có hai ô trống. )

Đây là thuật toán cơ bản mà các chương trình Scrabble AI chuyên nghiệp sử dụng, mặc dù tất nhiên chúng cũng phải xử lý những thứ như vị trí bảng, quản lý giá đỡ, v.v., điều này làm phức tạp các thuật toán đôi chút. Phiên bản đơn giản này của thuật toán sẽ đủ nhanh để tạo ra tất cả các từ có thể có trên một giá đỡ.

Đừng quên rằng tất nhiên bạn chỉ phải tính trie / dawg một lần nếu từ điển không thay đổi theo thời gian. Có thể tốn thời gian để xây dựng trie ra khỏi từ điển, vì vậy bạn có thể muốn làm như vậy một lần và sau đó tìm ra một số cách để lưu trữ trie trên đĩa ở dạng có thể sử dụng để tạo lại nó một cách nhanh chóng từ đĩa.

Bạn có thể tối ưu hóa việc sử dụng bộ nhớ bằng cách xây dựng DAWG từ bộ ba. Chú ý rằng có rất nhiều sự lặp lại vì trong tiếng Anh, rất nhiều từ end giống nhau, cũng giống như rất nhiều từ bắt đầu như nhau. Bộ ba thực hiện một công việc tuyệt vời trong việc chia sẻ các nút ở phần đầu nhưng lại tệ hại khi chia sẻ chúng ở phần cuối. Ví dụ:bạn có thể nhận thấy rằng mẫu "S $ không có con" là cực kỳ phổ biến và biến trie thành:

           ^root^
          / |  \
        O   P    S
        |   |   / \
        P$  O  O   T   
       /  \ |  |   |
      T$  | T$ P$  O
      |    \ | |   |
       \    \| /   P$
        \    |/    |
         \   |    /
          \  |   /  
           \ |  /
            \| /  
             |/
             |       
             S$

Tiết kiệm cả đống nút. Và sau đó, bạn có thể nhận thấy rằng hai từ bây giờ kết thúc bằng O-P $ -S $ và hai từ kết thúc bằng T $ -S $, vì vậy bạn có thể nén thêm thành:

           ^root^
           / | \
          O  P  S
          |  | / \
          P$ O \  T   
         /  \|  \ |
         |   |   \|
         |   |    O
         |   T$   |
          \  |    P$
           \ |   /
            \|  /  
             | /
             |/   
             S$

Và bây giờ chúng tôi có DAWG tối thiểu cho từ điển này.

Đọc thêm:

http://dl.acm.org/citation.cfm?id=42420

http://archive.msdn.microsoft.com/dawg1

http://www.gtoal.com/wordgames/scrabble.html