मैं समानता के लिए वाक्यांशों की तुलना कैसे करूं?

Question

कोई प्रश्न दर्ज करते समय, स्टैकओवरफ्लो आपको उन प्रश्नों की एक सूची प्रस्तुत करता है जो सोचते हैं कि एक ही विषय को कवर करने की संभावना है। मैंने अन्य साइटों या अन्य कार्यक्रमों में भी इसी तरह की विशेषताओं को देखा है, उदाहरण के लिए (सहायता फ़ाइल सिस्टम), लेकिन मैंने कभी ऐसा कुछ प्रोग्राम नहीं किया है। अब मुझे यह जानकर उत्सुकता है कि किस प्रकार का एल्गोरिदम इसका उपयोग करेगा।

मेरे दिमाग में आने वाला पहला दृष्टिकोण वाक्यांशों को शब्दों में विभाजित कर रहा है और इन शब्दों वाले वाक्यांशों को देख रहा है। ऐसा करने से पहले, आप शायद महत्वहीन शब्दों को फेंकना चाहते हैं (जैसे 'द', 'ए', 'करता है'), और फिर आप परिणाम रैंक करना चाहते हैं।

अरे, इंतजार - के वेब पन्नों के लिए है कि करते हैं, और फिर हम एक ... watchamacallit ... हो सकता है - एक "इंजन खोज", और फिर हम विज्ञापनों को बेच सकते हैं, और फिर ...

नहीं, गंभीरता से, इस समस्या को हल करने के सामान्य तरीके क्या हैं?

Answer 1

एक दृष्टिकोण तथाकथित बैग-ऑफ-शब्द मॉडल है।

जैसा कि आपने अनुमान लगाया था, पहले आप मानते हैं कि टेक्स्ट में कितनी बार शब्द दिखाई देते हैं (आमतौर पर एनएलपी-लिंगो में दस्तावेज़ कहा जाता है)। फिर आप तथाकथित स्टॉप शब्दों को फेंक देते हैं, जैसे कि "द", "ए", "या" और इसी तरह।

आप शब्दों और शब्द गणना के साथ छोड़ दिया गया है। थोड़ी देर के लिए ऐसा करें और आपको अपने दस्तावेज़ों में दिखाई देने वाले शब्दों का एक व्यापक समूह मिलता है। इसके बाद आप इन शब्दों के लिए एक इंडेक्स बना सकते हैं: "आर्डवार्क" 1 है, "सेब" 2 है ..., "जेड-इंडेक्स" 70092 है।

अब आप अपना शब्द बैग ले सकते हैं और उन्हें चालू कर सकते हैं वैक्टर। इस के बाद

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

आप a dot product के साथ दो वैक्टर के बीच "कोण" भरोसा कर सकते हैं: उदाहरण के लिए, अपने दस्तावेज़ aardvarks और कुछ नहीं के लिए दो संदर्भ शामिल हैं, तो यह इस प्रकार दिखाई देगा। कोण जितना छोटा होगा, उतने ही दस्तावेज हैं।

यह एक साधारण संस्करण है और वहां अन्य उन्नत तकनीकें हैं। Wikipedia be with you मई।

Answer 2

मेरे (बल्कि छोटे) अनुभव से पूर्ण-पाठ खोज इंजन विकसित करना: मैं उन प्रश्नों को देखता हूं जिनमें क्वेरी से कुछ शब्द होते हैं (आपके मामले में, क्वेरी आपका प्रश्न है)। निश्चित रूप से, शोर शब्दों को अनदेखा किया जाना चाहिए और हम खोज क्षेत्र को कम करने के लिए 'एएसपी.Net' जैसे 'मजबूत' शब्दों के लिए क्वेरी जांचना चाहेंगे। http://en.wikipedia.org/wiki/Index_(search_engine)#Inverted_indices'>Inverted अनुक्रमित सामान्यतः शब्द हम में रुचि रखते हैं के साथ सवालों को खोजने के लिए किया जाता है।

क्वेरी से शब्दों के साथ सवाल खोजने के बाद, हम हो सकता है प्रश्नों में रुचि रखने वाले शब्दों के बीच दूरी की गणना करना चाहते हैं, इसलिए 'वाक्यांश समानता' टेक्स्ट के साथ प्रश्न 'समानता पर चर्चा करने, आप निम्नलिखित वाक्यांशों को सुनते हैं ...' पाठ के साथ प्रश्न से अधिक है।

Answer 3

@ हनो आपको लेवेनशेटिन दूरी एल्गोरिदम का प्रयास करना चाहिए। एक इनपुट स्ट्रिंग रों और तार टी प्रत्येक स्ट्रिंग यूटी में के लिए पुनरावृति की की एक सूची को देखते हुए और न्यूनतम Levenshtein दूरी के साथ एक वापसी।,

कुछ तरीके हैं जिन्हें आप भी करने के लिए एन-ग्राम कुछ ध्यान देना कर सकते हैं:

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

http://www.javalobby.org/java/forums/t15908.html

Answer 4

में एक जावा कार्यान्वयन उदाहरण देखें बैग कई शब्द विचार बढ़ाने के लिए आदेश में रखा दो या दो से अधिक शब्दों के तार। आप ऐसा इसलिए करना चाहेंगे क्योंकि "अंतरिक्ष जटिलता" की खोज "अंतरिक्ष" और "जटिलता" वाले चीज़ों की खोज से कहीं अधिक है, क्योंकि इस वाक्यांश का अर्थ इसके हिस्सों की तुलना में अधिक है; यानी, यदि आपको कोई परिणाम मिलता है जो बाहरी अंतरिक्ष और ब्रह्मांड की जटिलता के बारे में बात करता है, तो शायद यह नहीं है कि "अंतरिक्ष जटिलता" की खोज वास्तव में क्या थी।

प्राकृतिक भाषा प्रसंस्करण से यहां एक महत्वपूर्ण विचार mutual information है, जो आपको (एल्गोरिदमिक रूप से) यह तय करने की अनुमति देता है कि वाक्यांश वास्तव में एक विशिष्ट वाक्यांश है (जैसे "अंतरिक्ष जटिलता") या केवल शब्द जो संयोग से निकट हैं । गणितीय रूप से, मुख्य विचार पूछना है, संभाव्य रूप से, यदि ये शब्द एक-दूसरे के बगल में दिखाई देते हैं तो आप अक्सर उनकी आवृत्तियों से अनुमान लगाएंगे। यदि आपको अपनी खोज क्वेरी (या अनुक्रमण के दौरान) में उच्च पारस्परिक जानकारी स्कोर वाला वाक्यांश दिखाई देता है, तो आप इन शब्दों को क्रम में रखने की कोशिश करके बेहतर परिणाम प्राप्त कर सकते हैं।