Làm thế nào để sửa đầu vào của người dùng (Loại google "ý bạn là gì?")

Question

Tôi có các yêu cầu sau: -

Tôi có nhiều (1 triệu) giá trị (tên). Người dùng sẽ nhập chuỗi tìm kiếm.

Tôi không mong đợi người dùng đánh vần tên chính xác.

Vì vậy, tôi muốn biến Google thành "Ý của bạn là". Điều này sẽ liệt kê tất cả các giá trị có thể từ kho dữ liệu của tôi. Có một câu hỏi tương tự nhưng không giống nhau here. Điều này không trả lời câu hỏi của tôi.

Câu hỏi của tôi: - 1) Tôi nghĩ rằng không nên lưu trữ những dữ liệu đó trong RDBMS. Bởi vì sau đó tôi sẽ không có bộ lọc trên các truy vấn SQL. Và tôi phải quét toàn bộ bảng. Vì vậy, trong tình huống này, cách dữ liệu sẽ được lưu trữ?

2) Câu hỏi thứ hai là giống như this. Nhưng, chỉ cho sự hoàn chỉnh của câu hỏi của tôi: làm cách nào để tìm kiếm thông qua tập dữ liệu lớn? Giả sử, có một tên Franky trong tập dữ liệu. Nếu người dùng nhập là Phranky, tôi làm cách nào để khớp với Franky? Tôi có phải lặp qua tất cả các tên không?

Tôi đã xem qua Levenshtein Distance, đây sẽ là một kỹ thuật tốt để tìm các chuỗi có thể. Nhưng một lần nữa, câu hỏi của tôi là tôi phải hoạt động trên tất cả 1 triệu giá trị từ kho dữ liệu của tôi?

3) Tôi biết, Google làm điều đó bằng cách xem hành vi của người dùng. Nhưng tôi muốn làm điều đó mà không xem hành vi của người dùng, tức là bằng cách sử dụng, tôi chưa biết, hãy nói thuật toán khoảng cách. Bởi vì phương pháp cũ sẽ yêu cầu khối lượng lớn các tìm kiếm để bắt đầu!

4) Như Kirk Broadhurst chỉ ra trong một câu trả lời below, có hai kịch bản có thể: -

• Người dùng đánh nhầm một từ (một chỉnh sửa khoảng cách thuật toán)
• Người dùng không biết một từ và đoán (một thuật toán đối sánh ngữ âm)

Tôi quan tâm đến cả hai. Họ thực sự là hai điều riêng biệt; ví dụ. Sean và Shawn âm thanh giống nhau nhưng có một khoảng cách chỉnh sửa 3 - quá cao để được coi là một lỗi đánh máy.

Answer 1

Thuật toán Soundex có thể giúp bạn giải quyết vấn đề này.

http://en.wikipedia.org/wiki/Soundex

Bạn có thể pre-tạo ra các giá trị Soundex cho mỗi tên và lưu nó trong cơ sở dữ liệu, sau đó chỉ số đó để tránh phải quét bàn.

Answer 2

Đây là vấn đề cũ, DWIM (Thực hiện ý nghĩa của tôi), được triển khai nổi tiếng trên Xerox Alto của Warren Teitelman. Nếu vấn đề của bạn được dựa trên cách phát âm, đây là một bài báo nghiên cứu có thể giúp:

J. Zobel và P. Dart "phiên âm Chuỗi Matching: Bài học từ thông tin Retieval," Proc. 19 hàng năm Inter. ACM SIGIR Conf. về Nghiên cứu và Phát triển trong Thu hồi Thông tin (SIGIR'96), tháng 8 năm 1996, trang 166-172.

Tôi được bạn bè của tôi làm việc trong việc thu thập thông tin rằng Soundex như được mô tả bởi Knuth hiện được coi là lỗi thời.

Answer 3

Tôi sẽ xem xét sử dụng giải pháp có sẵn cho việc này.

Aspell với custom dictionary tên có thể rất phù hợp cho việc này. Việc tạo tệp từ điển sẽ tính toán trước tất cả thông tin cần thiết để nhanh chóng đưa ra đề xuất.

Answer 4

Bitap Algorithm được thiết kế để tìm một kết quả gần đúng trong nội dung văn bản. Có lẽ bạn có thể sử dụng nó để tính toán các kết quả có thể xảy ra. (Nó dựa trên Levenshtein Distance)

(Cập nhật: sau khi đã đọc Ben Sanswer (sử dụng một giải pháp hiện có, có thể aspell) là con đường để đi)

---

Như những người khác cho biết, Google không chỉnh tự động bởi xem người dùng tự sửa. Nếu tôi tìm kiếm "someting" (sic) và sau đó ngay lập tức cho "something", rất có thể truy vấn đầu tiên không chính xác. Một heuristic, có thể phát hiện này sẽ là:

• Nếu người dùng đã thực hiện hai tìm kiếm trong một cửa sổ thời gian ngắn, và
• truy vấn đầu tiên không mang lại bất kỳ kết quả (hoặc người dùng không click vào bất cứ điều gì)
• truy vấn thứ hai đã làm sản lượng kết quả hữu ích
• hai truy vấn tương tự (có một khoảng cách Levenshtein nhỏ)

sau đó truy vấn thứ hai là một tinh thể của truy vấn đầu tiên mà bạn có thể lưu trữ và trước được gửi tới những người dùng khác.

Lưu ý rằng bạn có thể cần lô truy vấn để thu thập đủ dữ liệu để những đề xuất này hữu ích.

Answer 5

Chỉ cần sử dụng Solr hoặc máy chủ tìm kiếm tương tự và sau đó bạn sẽ không phải là chuyên gia trong chủ đề. Với danh sách đề xuất chính tả, hãy chạy tìm kiếm với từng kết quả được đề xuất và nếu có nhiều kết quả hơn truy vấn tìm kiếm hiện tại, hãy thêm kết quả đó dưới dạng kết quả "ý của bạn". (Điều này ngăn chặn các đề xuất chính tả không có thật mà không thực sự trả về các lần truy cập phù hợp hơn.) Bằng cách này, bạn không cần nhiều dữ liệu để thu thập để tạo ra một đề xuất ban đầu. có thể điều chỉnh kết quả của một số truy vấn nhất định.

Nói chung, bạn sẽ không sử dụng RDBMS cho loại tìm kiếm này, thay vào đó tùy thuộc vào cơ sở dữ liệu chỉ đọc, hơi cũ dành cho mục đích này. Trên trang Web cho công ty mà tôi làm việc, một dịch vụ hàng đêm chọn các bản ghi thay đổi từ RDBMS và đẩy chúng như một tài liệu vào Solr. Với rất ít nỗ lực, chúng tôi có một hệ thống nơi hộp tìm kiếm có thể tìm kiếm sản phẩm, đánh giá của khách hàng, trang web và mục blog rất hiệu quả và đưa ra đề xuất chính tả trong kết quả tìm kiếm cũng như duyệt qua mặt như bạn thấy tại NewEgg, Netflix hoặc Home Depot, với rất ít sự căng thẳng trên máy chủ (đặc biệt là RDBMS). (Tôi tin rằng cả Zappo [trang web mới] và Netflix đều sử dụng Solr trong nội bộ, nhưng không báo cho tôi về điều đó.)

Trong trường hợp của bạn, bạn muốn điền chỉ mục Solr với danh sách tên và chọn thuật toán khớp thích hợp trong tệp cấu hình.

Answer 6

Giống như một trong các câu trả lời cho câu hỏi mà bạn tham khảo, số great solution của Peter Norvig sẽ hoạt động với điều này, hoàn chỉnh với mã Python. Google có thể đưa ra gợi ý truy vấn một số cách, nhưng điều họ muốn cho họ là rất nhiều dữ liệu. Chắc chắn họ có thể đi mô hình hành vi người dùng với các bản ghi truy vấn rất lớn, nhưng họ cũng có thể chỉ sử dụng dữ liệu văn bản để tìm chính tả có khả năng chính xác nhất cho một từ bằng cách xem sửa chữa nào phổ biến hơn. Từ someting không xuất hiện trong từ điển và mặc dù đó là lỗi chính tả phổ biến, chính tả chính xác phổ biến hơn nhiều. Khi bạn tìm các từ tương tự, bạn muốn từ đó gần nhất với lỗi chính tả và có thể xảy ra nhất trong ngữ cảnh đã cho.

Giải pháp của Norvig là lấy một tập hợp các sách từ Project Gutenberg và đếm các từ xuất hiện. Từ những từ đó ông tạo ra một từ điển, nơi bạn cũng có thể ước tính xác suất của một từ (COUNT(word)/COUNT(all words)). Nếu bạn lưu trữ tất cả điều này dưới dạng băm thẳng, quyền truy cập nhanh, nhưng bộ nhớ có thể trở thành sự cố, vì vậy bạn cũng có thể sử dụng những thứ như suffix tries. Thời gian truy cập vẫn như cũ (nếu bạn triển khai nó dựa trên băm), nhưng yêu cầu lưu trữ có thể ít hơn nhiều.

Tiếp theo, anh tạo các chỉnh sửa đơn giản cho từ khóa chính tả (bằng cách xóa, thêm hoặc thay thế một chữ cái) và sau đó hạn chế danh sách các khả năng sử dụng từ điển từ kho văn bản. Điều này được dựa trên ý tưởng về khoảng cách chỉnh sửa (chẳng hạn như khoảng cách Levenshtein), với giả thuyết đơn giản rằng hầu hết các lỗi chính tả diễn ra với khoảng cách chỉnh sửa từ 2 trở xuống. Bạn có thể mở rộng này như nhu cầu của bạn và quyền lực tính toán ra lệnh.

Khi có những từ có thể, anh ta tìm thấy từ có thể xảy ra nhất từ ​​kho văn bản và đó là gợi ý của bạn. Có nhiều thứ bạn có thể thêm để cải thiện mô hình. Ví dụ: bạn cũng có thể điều chỉnh xác suất bằng cách xem xét khoảng cách bàn phím của các chữ cái trong lỗi chính tả. Tất nhiên, điều đó giả định người dùng đang sử dụng bàn phím QWERTY bằng tiếng Anh. Ví dụ: chuyển một số e và một số q có nhiều khả năng chuyển đổi e và l.

Answer 7

Đối với những người giới thiệu Soundex, nó đã hết hạn. Metaphone (đơn giản hơn) hoặc Double Metaphone (phức tạp) là tốt hơn nhiều. Nếu nó thực sự là dữ liệu tên, nó sẽ hoạt động tốt, nếu các tên có nguồn gốc châu Âu, hoặc ít nhất là phiên âm.

Đối với tìm kiếm, nếu bạn quan tâm đến việc cuộn, thay vì sử dụng Aspell hoặc một số cấu trúc dữ liệu thông minh khác ... tính toán trước các kết quả có thể là O (n^2), trong trường hợp ngây thơ, nhưng chúng tôi biết để phù hợp với tất cả, họ phải có một "âm vị" chồng lên nhau, hoặc thậm chí có thể hai. Bước lập chỉ mục trước này (có tỷ lệ dương sai thấp) có thể làm giảm độ phức tạp (trong trường hợp thực tế, giống như O (30^2 * k^2), trong đó k là < < n).

Answer 8

Bạn có hai vấn đề có thể là bạn cần phải giải quyết (hoặc không giải quyết nếu bạn lựa chọn)

1. Người dùng đánh nhầm một từ (một thuật toán chỉnh sửa khoảng cách)
2. Người dùng không biết một từ và đoán (một thuật toán đối sánh ngữ âm)

Bạn có quan tâm đến cả hai loại này hay chỉ một cách khác? Họ thực sự là hai điều riêng biệt; ví dụ. Sean và Shawn âm thanh giống nhau nhưng có một khoảng cách chỉnh sửa 3 - quá cao để được coi là một lỗi đánh máy.

Bạn nên lập chỉ mục số lượng từ để đảm bảo bạn chỉ đề xuất các câu trả lời có liên quan (tương tự như đề xuất của người phục tùng). Ví dụ: nếu tôi đã nhập sith Tôi có thể được hỏi nếu tôi có nghĩa là smith, tuy nhiên nếu tôi nhập smith thì sẽ không có ý nghĩa khi đề xuất sith. Xác định thuật toán đo lường khả năng tương đối của một từ và chỉ đề xuất các từ là nhiều khả năng là.

Kinh nghiệm của tôi về kết hợp lỏng lẻo được củng cố một cách học đơn giản nhưng quan trọng - thực hiện nhiều lớp lập chỉ mục/sàng khi bạn cần và đừng sợ bao gồm hơn 2 hoặc 3. Hãy loại bỏ mọi thứ không bắt đầu bằng đúng chữ cái, ví dụ, sau đó cull tất cả mọi thứ mà không kết thúc bằng chữ chính xác, và như vậy. Bạn thực sự chỉ muốn thực hiện tính toán khoảng cách chỉnh sửa trên tập dữ liệu nhỏ nhất có thể vì nó là một hoạt động rất chuyên sâu. Vì vậy, nếu bạn có một thuật toán O (n), O (nlogn) và O (n^2) - thực hiện cả ba, theo thứ tự đó, để đảm bảo bạn chỉ đặt 'triển vọng tốt' của bạn thông qua với thuật toán nặng của bạn.