स्ट्रिंग लम्बाई के बजाय अधिकतम संरेखण लंबाई के लिए लेवेनशेटिन दूरी को सामान्य कैसे करें?

Question

समस्या: कुछ आर पैकेजों में दो तारों की समानता की गणना करने के लिए लेवेनशेटिन दूरी कार्यान्वयन की सुविधा है, उदा। http://finzi.psych.upenn.edu/R/library/RecordLinkage/html/strcmp.html। गणना की दूरी को स्ट्रिंग लंबाई के लिए आसानी से सामान्यीकृत किया जा सकता है, उदा। लेवेनशेटिन दूरी को सबसे लंबी स्ट्रिंग की लंबाई से विभाजित करके या दो तारों की लंबाई के माध्यम से इसे विभाजित करके। भाषा विज्ञान में कुछ अनुप्रयोगों के लिए (उदा। डायलेक्टोमेट्री और ग्रहणशील बहुभाषी अनुसंधान), हालांकि, यह अनुशंसा की जाती है कि कच्चे लेवेनशेटिन दूरी को सबसे लंबे समय तक कम लागत वाले संरेखण (हेरिंगा, 2004: 130-132) की लंबाई के लिए सामान्यीकृत किया जाए। यह दूरी उपायों का उत्पादन करता है जो एक अवधारणात्मक भाषाई दृष्टिकोण से अधिक समझ में आता है।

उदाहरण: जर्मन स्ट्रिंग "tsYklUs" (Zyklus = चक्र) दो सम्मिलन के साथ एक 7-स्लॉट संरेखण में अपने स्वीडिश सजातीय "sYkEl" (cyckel = (बीआई) चक्र) में बदला जा सकता (आई) और दो प्रतिस्थापन (एस) 4. सामान्यीकृत Levenshtein दूरी की कुल परिवर्तन लागत के लिए: 4/7

(ए)

t--s--Y--k--l--U--s 
---s--Y--k--E--l--- 
=================== 
I-----------S--S--I = 4 

यह भी संभव है एक 8 स्लॉट संरेखण में तार कन्वर्ट करने के लिए 3 प्रविष्टि (I) और 1 विलोपन (डी) के साथ, कुल संरेखण लागत 4 के लिए भी। सामान्यीकृत Levenshtein दूरी: 4/8

(बी)

t--s--Y--k-----l--U--S 
---s--Y--k--E--l------ 
====================== 
I-----------D-----I--I = 4 

बाद संरेखण क्योंकि यह संरेखित करता है [l] और अधिक समझ में भाषायी, बनाता है बल्कि साथ [ई] की तुलना में एक दूसरे के साथ -phonemes और [यू] स्वर।

प्रश्न: किसी को भी किसी भी आर समारोह है कि मुझे सबसे लंबे समय तक कम से कम लागत वाली संरेखण के लिए के बजाय उचित स्ट्रिंग की लंबाई के लिए Levenshtein दूरी को सामान्य करने की अनुमति होगी के बारे में पता है? आपके इनपुट के लिए धन्यवाद!

संदर्भ: W.J. Heeringa (2004), मापने Levenshtein दूरी का उपयोग कर बोली उच्चारण मतभेद। पीएचडी थीसिस, ग्रोनिंगेन विश्वविद्यालय। http://www.let.rug.nl/~heeringa/dialectology/thesis/

संपादित करें - समाधान: मुझे लगता है कि मैंने एक समाधान निकाला है। adist फ़ंक्शन संरेखण वापस कर सकता है और सबसे लंबे समय तक कम लागत वाले संरेखण के लिए डिफ़ॉल्ट रूप से प्रतीत होता है।ऊपर के उदाहरण का समय लग करने के लिए यहां tsyklus करने के लिए sykel के साथ जुड़े संरेखण है:

> attr(adist("sykel", "tsyklus", counts = TRUE), "trafos") 
    [,1]  
[1,] "IMMMDMII" 

लंबाई-सामान्यीकृत दूरी की गणना करने के लिए के रूप में Heeringa (2004) द्वारा सिफारिश की है, हम एक मामूली समारोह लिख सकते हैं:

normLev.fnc <- function(a, b) { 
    drop(adist(a, b)/nchar(attr(adist(a, b, counts = TRUE), "trafos"))) 
} 

ऊपर के उदाहरण के लिए, यह रिटर्न

> normLev.fnc("sykel", "tsyklus") 
[1] 0.5 

यह फ़ंक्शन LSO रिटर्न Heeringa के लिए सही सामान्यीकृत दूरी (2004: 131) उदाहरण:

> normLev.fnc("bine", "bEi") 
[1] 0.6 
> normLev.fnc("kaninçen", "konEin") 
[1] 0.5555556 
> normLev.fnc("kenEeri", "kenArje") 
[1] 0.5 

तार के कई जोड़े की तुलना करना:

> L1 <- c("bine", "kaninçen", "kenEeri") 
> L2 <- c("bEi", "konEin", "kenArje") 
> diag(normLev.fnc(L1, L2)) 
[1] 0.6000000 0.5555556 0.5000000 

Answer 1

मामले में किसी भी भाषाविदों इस पोस्ट पर आते हैं, मैं करना चाहते हैं का कहना है कि RecordLinkage पैकेज द्वारा प्रदान की एल्गोरिदम गैर- ASCII तार की तुलना के लिए जरूरी इष्टतम नहीं हैं, उदाहरण के लिए:

> levenshteinSim("väg", "way") 
[1] -0.3333333 
> levenshteinDist("väg", "way") 
[1] 4 
> levenshteinDist("väg", "wäy") 
[1] 2 
> levenshteinDist("väg", "wüy") 
[1] 3