algorithm - "Absolute" string metric -

मेरे पास एक विशाल (लेकिन परिमित) प्राकृतिक भाषा स्ट्रिंग्स का सेट है।

मुझे एक तरीका है प्रत्येक स्ट्रिंग को एक संख्यात्मक मान में कनवर्ट करें किसी भी दिए गए स्ट्रिंग के लिए हर बार मूल्य वही होना चाहिए।

अधिक "अलग" दो दिए गए स्ट्रिंग्स हैं, अधिक भिन्न दो संगत मान होना चाहिए। अधिक "समान" वे हैं, कम अलग-अलग मान होना चाहिए।

मुझे अभी तक पता नहीं है कि मुझे स्ट्रिंग्स के बीच के अंतर की सटीक परिभाषा क्या है I need। वैसे भी कोई प्राकृतिक भाषा पार्स नहीं करती। शायद लेवेनस्टिन जैसी कुछ होनी चाहिए (लेकिन लेवेनस्टीन रिश्तेदार है और मुझे पूर्ण मीट्रिक चाहिए) चलो कुछ सरलता से शुरू करते हैं।

आयामों पर अपडेट

मुझे एक संख्यात्मक मान के बजाय बहुआयामी (3 डी सबसे अच्छा) वेक्टर के लिए व्यवस्थित होने में खुशी होगी।

< एच 2> अपेक्षित परिणाम शुद्धता पर अद्यतन

जैसा कि यह ठीक से नोट किया गया था और, एक स्ट्रिंग से दूसरे में दूरी MAX (प्रथम स्ट्रिंग लाईन्ग, सेकंड स्ट्रिंग लैंप) वाले वेक्टर है आयाम सामान्य तौर पर कुछ नुकसान की जानकारी के बिना आयामों की संख्या को कम करना संभव नहीं है।

हालांकि मुझे एक पूर्ण समाधान की आवश्यकता नहीं है मैं किसी भी "अच्छा पर्याप्त" रूपांतरण के लिए N-dimensional तार अंतरिक्ष से मेरे 3 डी अंतरिक्ष में व्यवस्थित होगा।

यह भी ध्यान दें कि मेरे पास सीमित लंबाई के तार की एक सीमित संख्या है (स्ट्रिंग्स की संख्या हालांकि बड़ी है, लगभग 80 मिलियन (10 जीबी), इसलिए मैं कुछ सिंगल-पास राज्य-कम एल्गोरिथम चुनना चाहता हूं।)

स्कैनिंग संदर्भों से, मुझे लगता है कि मुझे यहाँ मदद कर सकता है ऐसा लगता है कि लेख मेरी समस्या के करीब कुछ पर चर्चा करता है ...

हिल्बर्ट वक्र दृष्टिकोण पर अपडेट

1. हम प्रत्येक स्ट्रिंग को किसी बिंदु पर एन-डायमेंशनल स्पेस में मैप करते हैं, जहां N सेट में एक स्ट्रिंग की अधिकतम लंबाई है। बीटीडब्लू, क्या आई-वें अक्षर कोड को आई-वें समन्वय मूल्य के रूप में इस्तेमाल किया जा सकता है?
2. हम उस एन-डायमेंशनल स्पेस के माध्यम से एक हिल्बर्ट वक्र की साजिश करते हैं।
3. प्रत्येक के लिए स्ट्रिंग हम वक्र पर बिंदु लेते हैं, स्ट्रिंग के निर्देशांक के निकटतम। उस बिंदु का हिल्बर्ट मान (वक्र की शुरुआत से लंबाई) मैं चाहता हूं कि एकल-आयामी मूल्य है।
4. यदि हमें 3 डी मान की आवश्यकता है, तो हम हिल्बर्ट वक्र को 3 डी में पलायन करते हैं और पॉइंट्स चुनते हैं, हिल्बर्ट मान से मिलान करते हैं, ऊपर की गणना।

क्या यह सही दिखता है? कम्प्यूटेशनल व्यय क्या होगा?

मुझे नहीं लगता कि यह करना संभव है। एक सरल स्ट्रिंग के साथ शुरू करो, और इसे शून्य निर्दिष्ट करें (यह वास्तव में कोई फर्क नहीं पड़ता कि नंबर क्या है)

• "हैलो वर्ल्ड" = 0

निम्नलिखित स्ट्रिंग्स इसे से 2 दूरी पर हैं:

• "XXllo World" = a
• "HeXXo World" = b
• "हैलो XXrld" =
• "नमस्ते वार्ज़ैस" = डी

फिर भी, ये प्रत्येक स्ट्रिंग एक दूसरे से 4 है। निम्नलिखित उदाहरण के लिए संख्याओं को क्रमबद्ध करने का कोई तरीका नहीं है:

a = 1, b = -1, c = 2, d = 2

विचार करें कि 0 से 2 है, फिर भी 1 से 1 है, फिर भी 0 एक से करीब है।

और ये सिर्फ एक सरल मामला है।