Làm cách nào để so sánh các cụm từ cho sự giống nhau?

Question

Khi nhập câu hỏi, stackoverflow trình bày cho bạn một danh sách các câu hỏi mà nó cho rằng có khả năng bao gồm cùng một chủ đề. Tôi cũng đã thấy các tính năng tương tự trên các trang khác hoặc trong các chương trình khác (ví dụ như hệ thống tập tin trợ giúp), nhưng tôi chưa bao giờ tự mình lập trình một cái gì đó như thế này. Bây giờ tôi tò mò muốn biết những gì sắp xếp của một thuật toán sẽ sử dụng cho điều đó.

Cách tiếp cận đầu tiên đến với tâm trí của tôi là chia cụm từ thành các từ và tìm cụm từ chứa các từ này. Trước khi bạn làm điều đó, bạn có thể muốn vứt bỏ những từ không đáng kể (như 'the', 'a', 'does' etc), và sau đó bạn sẽ muốn xếp hạng kết quả.

Hey, chờ đợi - chúng ta hãy làm điều đó cho các trang web, và sau đó chúng ta có thể có một ... watchamacallit ... - một "công cụ tìm kiếm", và sau đó chúng ta có thể bán quảng cáo, và sau đó ...

Không, nghiêm túc, cách phổ biến để giải quyết vấn đề này là gì?

Answer 1

Một cách tiếp cận được gọi là mô hình túi-của-từ.

Như bạn đã đoán, trước tiên bạn đếm số lần từ xuất hiện trong văn bản (thường được gọi là tài liệu trong NLP-lingo). Sau đó, bạn vứt bỏ những từ được gọi là "stop", chẳng hạn như "the", "a", "hoặc" v.v.

Bạn còn lại với các từ và số lượng từ. Thực hiện việc này một lúc và bạn nhận được một tập hợp các từ xuất hiện trong tài liệu của bạn. Sau đó, bạn có thể tạo chỉ mục cho những từ này: "aardvark" là 1, "apple" là 2, ..., "z-index" là 70092.

Bây giờ bạn có thể lấy túi từ và biến chúng thành vectơ. Ví dụ, nếu tài liệu của bạn chứa hai tài liệu tham khảo cho aardvarks và không có gì khác, nó sẽ trông như thế này:

[2 0 0 ... 70k zeroes ... 0]. 

Sau này bạn có thể đếm "góc" giữa hai vectơ với a dot product. Góc càng nhỏ, tài liệu càng gần.

Đây là phiên bản đơn giản và có các kỹ thuật nâng cao khác. Có thể số Wikipedia be with you.

Answer 2

Từ kinh nghiệm (khá nhỏ) của tôi phát triển công cụ tìm kiếm toàn văn: tôi sẽ tra cứu các câu hỏi có chứa một số từ truy vấn (trong trường hợp của bạn, truy vấn là câu hỏi của bạn). Chắc chắn, các từ tiếng ồn nên được bỏ qua và chúng tôi có thể muốn kiểm tra truy vấn cho các từ 'mạnh' như 'ASP.Net' để thu hẹp phạm vi tìm kiếm. http://en.wikipedia.org/wiki/Index_(search_engine)#Inverted_indices'>Các chỉ mục đảo ngược thường được sử dụng để tìm câu hỏi với các từ mà chúng tôi quan tâm.

Sau khi tìm câu hỏi với các từ trong truy vấn, chúng tôi có thể muốn tính toán khoảng cách giữa các từ mà chúng ta quan tâm trong các câu hỏi, do đó, câu hỏi với văn bản 'cụm từ tương tự' xếp hạng cao hơn câu hỏi với 'thảo luận tương tự, bạn nghe cụm từ sau ...' văn ​​bản.

Answer 3

@Bạn nên thử thuật toán khoảng cách Levenshtein. Với một chuỗi đầu vào s và một danh sách các chuỗi t lặp cho mỗi chuỗi u trong t và trả lại một với khoảng cách Levenshtein tối thiểu.

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

Xem một ví dụ thực hiện Java trong http://www.javalobby.org/java/forums/t15908.html

Answer 4

Để tăng cường cho túi-of-từ ý tưởng:

Có một vài cách để bạn cũng có thể trả một số sự chú ý đến n-gram, các chuỗi của hai hoặc nhiều từ được giữ theo thứ tự. Bạn có thể muốn làm điều này bởi vì tìm kiếm "không gian phức tạp" nhiều hơn tìm kiếm những thứ có "không gian" và "phức tạp" trong chúng, vì ý nghĩa của cụm từ này nhiều hơn tổng của các phần của nó; có nghĩa là, nếu bạn nhận được kết quả là nói về sự phức tạp của không gian bên ngoài và vũ trụ, điều này có lẽ không phải là tìm kiếm "không gian phức tạp" thực sự có ý nghĩa.

Ý tưởng chính từ xử lý ngôn ngữ tự nhiên ở đây là mutual information, cho phép bạn (thuật toán) đánh giá cụm từ có thực sự là cụm từ cụ thể (chẳng hạn như "không gian phức tạp") hay không. . Về mặt toán học, ý tưởng chính là hỏi, xác suất, nếu những từ này xuất hiện bên cạnh nhau thường xuyên hơn bạn sẽ đoán bằng tần số của chúng. Nếu bạn thấy cụm từ có điểm thông tin chung cao trong truy vấn tìm kiếm của bạn (hoặc trong khi lập chỉ mục), bạn có thể nhận được kết quả tốt hơn bằng cách cố gắng giữ các từ này theo thứ tự.