مسافة ليفنشتاين

في نظرية المعلومات ، وعلم اللغة ، وعلوم الحاسوب ، تُعدّ مسافة ليفنشتاين مقياسًا للسلاسل النصية يُستخدم لقياس الفرق بين سلسلتين. وتُعرّف مسافة ليفنشتاين بين كلمتين بأنها الحد الأدنى لعدد التعديلات على حرف واحد (إضافة، حذف، أو استبدال) اللازمة لتحويل إحدى الكلمتين إلى الأخرى. وقد سُمّيت هذه المسافة نسبةً إلى عالم الرياضيات السوفيتي فلاديمير ليفنشتاين ، الذي وضع تعريفها عام 1965. ^{[ 1 ]}

قد يُشار إلى مسافة ليفنشتاين أيضًا باسم مسافة التحرير ، على الرغم من أن هذا المصطلح قد يشير أيضًا إلى مجموعة أكبر من مقاييس المسافة. ^{[ 2 ]}^{: 32} وهي ترتبط ارتباطًا وثيقًا بمحاذاة السلاسل الثنائية .

تعريف

مسافة ليفنشتاين بين سلسلتين $a,b$ (طول) $|a|$ و $|b|$ (على التوالي) يُعطى بواسطة $\operatorname {lev} (a,b)$ أين

\operatorname {lev} (a,b)={\begin{cases}|a|&{\text{ إذا كان }}|b|=0,\\|b|&{\text{ إذا كان }}|a|=0,\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}&{\text{ إذا كان }}\operatorname {head} (a)=\operatorname {head} (b),\\1+\min {\begin{cases}\operatorname {lev} {\big (}\operatorname {tail} (a),b{\big )}\\\operatorname {lev} {\big (}a,\operatorname {tail} (b){\big )}\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}\\\end{cases}}&{\text{ otherwise}}\end{cases}}

حيث $\operatorname {tail}$ من بعض الخيوط $x$ هي سلسلة تتكون من جميع الأحرف باستثناء الحرف الأول من $x$ (أي $\operatorname {tail} (x_{0}x_{1}\dots x_{n})=x_{1}x_{2}\dots x_{n}$ )، و $\operatorname {head} (x)$ هو الحرف الأول من $x$ (أي $\operatorname {head} (x_{0}x_{1}\dots x_{n})=x_{0}$ ). إما الترميز $x[n]$ أو $x_{n}$ يُستخدم للإشارة إلى $n$ الحرف رقم 1 من السلسلة $x$ ، بدءًا من الصفر ، وبالتالي $\operatorname {head} (x)=x_{0}=x[0]$ .

العنصر الأول في الحد الأدنى يتوافق مع الحذف (من $a$ ل $b$ )، والثاني للإدخال والثالث للاستبدال.

يتوافق هذا التعريف بشكل مباشر مع التنفيذ التكراري البسيط .

التعبير الذي لا يحتوي على حالات خاصة هو: ${\begin{aligned}\operatorname {lev} (a,b)&=|a|+|b|-f(a,b)\\f(a,b)&=\max {\begin{cases}0\\1+f{\big (}\operatorname {tail} (a),b{\big )}\\1+f{\big (}a,\operatorname {tail} (b){\big )}\\1+{\big [}\operatorname {head} (a)=\operatorname {head} (b){\big ]}+f{\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}\end{cases}}\end{aligned}}$

مثال

على سبيل المثال، مسافة ليفنشتاين بين "kitten" و "sitting" هي 3، لأن التعديلات الثلاثة التالية تغير أحدهما إلى الآخر، ولا توجد طريقة للقيام بذلك بأقل من 3 تعديلات:

k itten → s itten (استبدال "s" بـ "k"),
sitt e n → sitt i n (استبدال "i" بـ "e")،
sittin → sittin g (إضافة حرف "g" في النهاية).

يمكن رؤية مثال بسيط على الحذف مع كلمتي "uninformed" و "uniformed" اللتين تبلغ المسافة بينهما 1:

uni n form → uniformed (حذف "n").

الحدود العليا والسفلى

تتضمن مسافة ليفنشتاين عدة حدود عليا وسفلى بسيطة، منها:

إنها على الأقل القيمة المطلقة للفرق بين حجمي السلسلتين.
لا يتجاوز طوله طول الخيط الأطول.
تكون القيمة صفرًا إذا وفقط إذا كانت السلاسل متساوية.
إذا كانت السلسلتان متساويتين في الطول، فإن مسافة هامينغ تمثل حدًا أعلى لمسافة ليفنشتاين. مسافة هامينغ هي عدد المواضع التي تختلف فيها الرموز المتناظرة في السلسلتين.
إن مسافة ليفنشتاين بين سلسلتين لا تزيد عن مجموع مسافات ليفنشتاين الخاصة بهما من سلسلة ثالثة ( متباينة المثلث ).

مثال على أن مسافة ليفنشتاين بين سلسلتين متساويتين في الطول أقل تمامًا من مسافة هامينغ هو الزوج "flaw" و"lawn". هنا، تساوي مسافة ليفنشتاين 2 (بحذف "f" من البداية وإضافة "n" في النهاية). أما مسافة هامينغ فهي 4.

التطبيقات

في مطابقة السلاسل التقريبية ، يكمن الهدف في إيجاد تطابقات لسلاسل نصية قصيرة ضمن نصوص طويلة متعددة، في حالات يُتوقع فيها وجود عدد قليل من الاختلافات. يمكن أن تأتي السلاسل القصيرة من قاموس، على سبيل المثال. في هذه الحالة، تكون إحدى السلاسل قصيرة عادةً، بينما تكون الأخرى طويلة بشكل عشوائي. لهذا النوع من المطابقة تطبيقات واسعة النطاق، منها على سبيل المثال: مدققات الإملاء ، وأنظمة تصحيح الأخطاء في التعرف الضوئي على الأحرف ، وبرامج مساعدة الترجمة الآلية للغات الطبيعية القائمة على ذاكرة الترجمة .

يمكن أيضًا حساب مسافة ليفنشتاين بين سلسلتين نصيتين طويلتين، لكن تكلفة حسابها، التي تتناسب تقريبًا مع حاصل ضرب طول السلسلتين، تجعل ذلك غير عملي. لذا، عند استخدامها للمساعدة في البحث التقريبي عن السلاسل النصية في تطبيقات مثل ربط السجلات ، عادةً ما تكون السلاسل النصية المُقارنة قصيرة لتحسين سرعة المقارنات.

في علم اللغة، تُستخدم مسافة ليفنشتاين كمقياس لتحديد المسافة اللغوية ، أو مدى اختلاف لغتين عن بعضهما البعض. ^{[ 3 ]} وهي مرتبطة بالفهم المتبادل : فكلما زادت المسافة اللغوية، قلّ الفهم المتبادل، والعكس صحيح.

يمكن استخدام مسافة ليفنشتاين لتقييم أداء المستمعين خلال اختبارات تمييز الكلام، وذلك في تطبيقات متنوعة مثل قياس السمع الكلامي. في هذا السياق، تُحسب مسافات ليفنشتاين لتحديد المسافة بين المحفزات المقدمة للمستمع وتسلسل الأصوات اللغوية التي تم تمييزها. قد تكون التكلفة المرتبطة باستبدال الأصوات اللغوية ثابتة أو تعتمد على عدد السمات الصوتية المختلفة بين الصوتين اللغويين المستبدلين. ^{[ 4 ]}

في المعلوماتية الحيوية ، تقيس مسافة ليفنشتاين والخوارزميات المشابهة الفرق بين التسلسلات البيولوجية، مثل تسلسلات الحمض النووي والبروتين . وتُقابل التعديلات في الخوارزمية الطفرات الجينية: إدخال أو حذف أو استبدال نيوكليوتيد ( في الحمض النووي) أو حمض أميني (في البروتين ). وقد تشير المسافة الأقصر بين تسلسلين إلى علاقة تطورية أو وظيفية أوثق. ^[⁵^]

العلاقة مع مقاييس مسافة التحرير الأخرى

توجد مقاييس أخرى شائعة لمسافة التحرير ، والتي تُحسب باستخدام مجموعة مختلفة من عمليات التحرير المسموح بها. على سبيل المثال:

تسمح مسافة داميراو-ليفنشتاين بنقل حرفين متجاورين إلى جانب الإدخال والحذف والاستبدال؛
تسمح مسافة أطول تسلسل فرعي مشترك (LCS) بالإدخال والحذف فقط، وليس الاستبدال؛
تسمح مسافة هامينغ بالاستبدال فقط، وبالتالي فهي تنطبق فقط على السلاسل ذات الطول نفسه.
تسمح مسافة جارو فقط بالتبديل .

تُعرَّف مسافة التحرير عادةً بأنها مقياس قابل للتحديد، يُحسب باستخدام مجموعة محددة من عمليات التحرير المسموح بها، وتُخصَّص لكل عملية تكلفة (قد تكون غير محدودة). ويُعمَّم هذا المفهوم بشكل أكبر بواسطة خوارزميات محاذاة تسلسل الحمض النووي ، مثل خوارزمية سميث-واترمان ، التي تجعل تكلفة العملية تعتمد على موضع تطبيقها.

حساب

التكراري

هذا تطبيق هاسكلlDistance بسيط ولكنه غير فعال، يعتمد على التكرار، لدالة تأخذ سلسلتين نصيتين، s و t ، مع أطوالهما، وتعيد مسافة ليفنشتاين بينهما:

lDistance::Eqa=>[a]->[a]->IntlDistance[]t=lengtht-- If s is empty, the distance is the number of characters in tlDistances[]=lengths-- If t is empty, the distance is the number of characters in slDistances@(a:s')t@(b:t')|a==b=lDistances't'-- If the first characters are the same, they can be ignored|otherwise=1+minimum-- Otherwise try all three possible actions and select the best one[lDistancest'-- Character is inserted (b inserted),lDistances't-- Character is deleted (a deleted),lDistances't'-- Character is replaced (a replaced with b)]

This implementation is very inefficient because it recomputes the Levenshtein distance of the same substrings many times.

A more efficient method would never repeat the same distance calculation. For example, the Levenshtein distance of all possible suffixes might be stored in an array $M$ , where $M[i][j]$ is the distance between the last $i$ characters of string s and the last $j$ characters of string t. The table is easy to construct one row at a time starting with row 0. When the entire table has been built, the desired distance is in the table in the last row and column, representing the distance between all of the characters in s and all the characters in t.

Iterative with full matrix

This section uses 1-based strings rather than 0-based strings. If m is a matrix, $m[i,j]$ is the ith row and the jth column of the matrix, with the first row having index 0 and the first column having index 0.

Computing the Levenshtein distance is based on the observation that if we reserve a matrix to hold the Levenshtein distances between all prefixes of the first string and all prefixes of the second, then we can compute the values in the matrix in a dynamic programming fashion, and thus find the distance between the two full strings as the last value computed.

تمت مناقشة هذه الخوارزمية، وهي مثال على البرمجة الديناميكية من الأسفل إلى الأعلى ، مع متغيرات، في مقالة عام 1974 بعنوان " مشكلة تصحيح السلسلة إلى السلسلة" بقلم روبرت أ. واغنر ومايكل ج. فيشر. ^{[ 6 ]}

هذا تطبيق بسيط لرمز زائف لدالة LevenshteinDistanceتأخذ سلسلتين نصيتين، s بطول m و t بطول n ، وتعيد مسافة ليفنشتاين بينهما:

دالة LevenshteinDistance ( char s [ 1..m ] , char t [ 1..n ] ) : // لكل i و j ، سيحتوي d [ i , j ] على مسافة ليفنشتاين بين // أول i حرف من s وأول j حرف من t . ...d[i,j]:=minimum(d[i-1,j]+1,// deletiond[i,j-1]+1,// insertiond[i-1,j-1]+substitutionCost)// substitutionreturnd[m,n]

Two examples of the resulting matrix (hovering over a tagged number reveals the operation performed to get that number):

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1	2	3	4	5
t	3	3	2	1	2	3	4
t	4	4	3	2	1	2	3
i	5	5	4	3	2	2	3
n	6	6	5	4	3	3	2
g	7	7	6	5	4	4	3

		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

The invariant maintained throughout the algorithm is that we can transform the initial segment s[1..i] into t[1..j] using a minimum of d[i,j] operations. At the end, the bottom-right element of the array contains the answer.

Iterative with two matrix rows

It turns out that only two rows of the table – the previous row and the current row being calculated – are needed for the construction, if one does not want to reconstruct the edited input strings.

The Levenshtein distance can be calculated iteratively using the following algorithm:^[7]

functionLevenshteinDistance(chars[0..m-1],chart[0..n-1]):// create two work vectors of integer distancesdeclareintv0[n+1]declareintv1[n+1]// initialize v0 (the previous row of distances)// this row is A[0][i]: edit distance from an empty s to t;// that distance is the number of characters to append to s to make t.forifrom0ton:v0[i]=iforifrom0tom-1:// calculate v1 (current row distances) from the previous row v0// first element of v1 is A[i + 1][0]// edit distance is delete (i + 1) chars from s to match empty tv1[0]=i+1// استخدم الصيغة لملء باقي الصف لـ j من 0 إلى n - 1 : // حساب التكاليف لـ A[i + 1][j + 1] تكلفة الحذف := v0 [ j + 1 ] + 1 تكلفة الإضافة := v1 [ j ] + 1 إذا كان s [ i ] = t [ j ] : تكلفة الاستبدال := v0 [ j ] وإلا : تكلفة الاستبدال := v0 [ j ] + 1v1 [ j + 1 ] := minimum ( deletionCost , insertionCost , substitutionCost )// نسخ v1 (الصف الحالي) إلى v0 (الصف السابق) للتكرار التالي // بما أن البيانات في v1 تُعتبر غير صالحة دائمًا، فإن التبديل بدون نسخ قد يكون أكثر كفاءة تبديل v0 مع v1 // بعد التبديل الأخير، تصبح نتائج v1 موجودة في v0 إرجاع v0 [ n ]

تجمع خوارزمية هيرشبرغ بين هذه الطريقة وأسلوب فرق تسد . ويمكنها حساب تسلسل التحرير الأمثل، وليس فقط مسافة التحرير، في نفس حدود الوقت والمساحة التقاربية. ^{[ 8 ]}

الأوتوماتا

تحدد آلات ليفنشتاين بكفاءة ما إذا كانت مسافة التحرير لسلسلة ما أقل من قيمة ثابتة معينة من سلسلة معينة. ^{[ 9 ]}

تقريب

يمكن تقريب مسافة ليفنشتاين بين سلسلتين طولهما $n$ ضمن عامل معين.

(\log n)^{O(1/\varepsilon )},

حيث $ε > 0$ هو مُعامل حر يُمكن ضبطه، في زمن $O (n 1 + ε)$ . ^{[ 10 ]} . بعد عشر سنوات، اكتشف الباحثون خوارزمية لها نفس زمن التشغيل ولكن بمعامل تقريب $f(1/ ε)$ ، لدالة $f$ تعتمد فقط على $ε$ ^{[ 11 ]} .

التعقيد الحسابي

لقد ثبت أنه لا يمكن حساب مسافة ليفنشتاين بين سلسلتين طول كل منهما $n في زمن$ $O (n² - ε)$ لأي قيمة ε أكبر من الصفر، إلا إذا كانت فرضية الزمن الأسي القوي خاطئة. ^{[ 12 ]} وهناك حد أدنى آخر (غير مشروط) لتعقيد هذه المسألة وهو $\Omega (mn)$ في نموذج يكون فيه الاستعلام الوحيد على رموز السلاسل هو مقارنة رمزين. ^{[ 13 ]}

انظر أيضاً

agrep
مطابقة السلاسل التقريبية
الفرق
التواء زمني ديناميكي
المسافة الإقليدية
تشابه التسلسلات في علم الوراثة
خوارزمية هانت-شيمانسكي
مؤشر جاكارد
مسافة جارو-وينكلر
التجزئة الحساسة للموقع
لوسين (محرك بحث مفتوح المصدر يطبق تقنية مسافة التحرير)
مسافة مانهاتن
المساحة المترية
مينهاش
التصنيف العددي
خوارزمية المطابقة المثلى
مؤشر التشابه لسورنسن

مراجع

↑ ف. إي. ليفنشتاين (1965).الرموز المزدوجة مع الرموز المجهزة والمثبتة والمؤقتة[ الرموز الثنائية قادرة على تصحيح عمليات الحذف والإدراج والعكس ] . Доклады Академии Наук СССР (باللغة الروسية). 163 (4): 845- 848.نُشر باللغة الإنجليزية بعنوان: ليفنشتاين، فلاديمير إي. (فبراير 1966). "الرموز الثنائية القادرة على تصحيح الحذف والإضافة والانعكاس". مجلة الفيزياء السوفيتية دوكلادي . 10 (8): 707-710 . رمز Bibcode : 1966SPhD...10..707L .
↑ نافارو، غونزالو (2001). "جولة إرشادية لتقريب مطابقة السلاسل النصية" (ملف PDF) . مجلة ACM Computing Surveys . 33 (1): 31-88 . CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224 .
↑ جان د. تين ثيج؛ لودجر زيفيرت (1 يناير 2007)، التعدد اللغوي الاستقبالي: التحليلات اللغوية، والسياسات اللغوية، والمفاهيم التعليمية ، شركة جون بنجامينز للنشر، رقم ISBN 978-90-272-1926-8بافتراض أن الفهم يتناسب عكسياً مع المسافة اللغوية... الكلمات الأساسية، نسبة الكلمات المتشابهة (المرتبطة مباشرة أو عبر المرادف)... الترابط المعجمي... الترابط النحوي.
↑ فونتان، ل.؛ فيراني، إ.؛ فاريناس، ج.؛ بينكييه، ج.؛ أومون، إكس. (2016). "استخدام مسافات ليفنشتاين الموزونة صوتيًا للتنبؤ بالوضوح المجهري". وقائع مؤتمر إنترسبيتش 2016: المؤتمر السنوي السابع عشر للجمعية الدولية للاتصالات الكلامية. إنترسبيتش 2016. سان فرانسيسكو، الولايات المتحدة الأمريكية. الصفحات 650-654 .
↑ بيرغر، بوني؛ ووترمان، مايكل س.؛ يو، يون ويليام (يونيو 2021). "مسافة ليفنشتاين، ومقارنة التسلسلات، والبحث في قواعد البيانات البيولوجية" . معاملات IEEE في نظرية المعلومات . 67 (6): 3287-3294 . doi : 10.1109/TIT.2020.2996543 . ISSN 1557-9654 . PMC 8274556 .
↑ فاغنر، روبرت أ.؛ فيشر، مايكل ج. (1974)، "مشكلة تصحيح السلسلة إلى السلسلة"، مجلة ACM ، 21 (1): 168-173 ، doi : 10.1145/321796.321811 ، S2CID 13381535
↑ هيلمكفيست، ستين (26 مارس 2012)، خوارزمية ليفنشتاين سريعة وفعالة من حيث الذاكرة.
↑ هيرشبرغ، د.س. (1975). "خوارزمية فضاء خطي لحساب المتتاليات الفرعية المشتركة القصوى" (ملف PDF) . اتصالات رابطة آلات الحوسبة ( مخطوطة مُقدَّمة). 18 (6): 341-343 . CiteSeerX 10.1.1.348.4774 . doi : 10.1145/360825.360861 . MR 0375829. S2CID 207694727 .
↑ شولز، كلاوس يو؛ ميهوف، ستويان (2002). "تصحيح سريع للسلاسل النصية باستخدام أوتوماتا ليفنشتاين". المجلة الدولية لتحليل المستندات والتعرف عليها . 5 (1): 67-85 . CiteSeerX 10.1.1.16.652 . doi : 10.1007/s10032-002-0082-8 . S2CID 207046453 .
↑ أندوني، ألكسندر؛ كراوثغامر، روبرت؛ أوناك، كريستوف (2010). تقريب متعدد اللوغاريتمات لمسافة التحرير وتعقيد الاستعلام غير المتماثل . ندوة IEEE حول أسس علوم الحاسوب (FOCS). arXiv : 1005.4033 . Bibcode : 2010arXiv1005.4033A . CiteSeerX : 10.1.1.208.2079 .
↑ أندوني، أ؛ نوساتزكي، ن (2020). مسافة التحرير في زمن شبه خطي: إنه عامل ثابت . ندوة IEEE حول أسس علوم الحاسوب (FOCS). arXiv : 2005.07678 .
↑ باكورس، أرتورس؛ إنديك، بيوتر (2015). لا يمكن حساب مسافة التحرير في وقت شبه تربيعي قوي (إلا إذا كانت SETH خاطئة) . المؤتمر السنوي السابع والأربعون لجمعية ACM حول نظرية الحوسبة (STOC). arXiv : 1412.0348 . Bibcode : 2014arXiv1412.0348B .
↑ وونغ، سي كيه؛ تشاندرا، أشوك كيه. (1976). "حدود مشكلة تحرير السلاسل النصية". مجلة ACM . 23 (1): 13-16 . doi : 10.1145/321921.321923 .

روابط خارجية

بلاك، بول إي، محرر (14 أغسطس 2008)، "مسافة ليفنشتاين"، قاموس الخوارزميات وهياكل البيانات [ عبر الإنترنت ] ، المعهد الوطني الأمريكي للمعايير والتكنولوجيا ، تم الاطلاع عليه في 2 نوفمبر 2016
تطبيقات برنامج Rosetta Code لمسافة ليفنشتاين

[1] ف. إي. ليفنشتاين (1965).الرموز المزدوجة مع الرموز المجهزة والمثبتة والمؤقتة[ الرموز الثنائية قادرة على تصحيح عمليات الحذف والإدراج والعكس ] . Доклады Академии Наук СССР (باللغة الروسية). 163 (4): 845- 848.نُشر باللغة الإنجليزية بعنوان: ليفنشتاين، فلاديمير إي. (فبراير 1966). "الرموز الثنائية القادرة على تصحيح الحذف والإضافة والانعكاس". مجلة الفيزياء السوفيتية دوكلادي . 10 (8): 707-710 . رمز Bibcode : 1966SPhD...10..707L .

[navarro-2] نافارو، غونزالو (2001). "جولة إرشادية لتقريب مطابقة السلاسل النصية" (ملف PDF) . مجلة ACM Computing Surveys . 33 (1): 31-88 . CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224 .

[ref05xubej-3] جان د. تين ثيج؛ لودجر زيفيرت (1 يناير 2007)، التعدد اللغوي الاستقبالي: التحليلات اللغوية، والسياسات اللغوية، والمفاهيم التعليمية ، شركة جون بنجامينز للنشر، رقم ISBN 978-90-272-1926-8بافتراض أن الفهم يتناسب عكسياً مع المسافة اللغوية... الكلمات الأساسية، نسبة الكلمات المتشابهة (المرتبطة مباشرة أو عبر المرادف)... الترابط المعجمي... الترابط النحوي.

[4] فونتان، ل.؛ فيراني، إ.؛ فاريناس، ج.؛ بينكييه، ج.؛ أومون، إكس. (2016). "استخدام مسافات ليفنشتاين الموزونة صوتيًا للتنبؤ بالوضوح المجهري". وقائع مؤتمر إنترسبيتش 2016: المؤتمر السنوي السابع عشر للجمعية الدولية للاتصالات الكلامية. إنترسبيتش 2016. سان فرانسيسكو، الولايات المتحدة الأمريكية. الصفحات 650-654 .

[5] بيرغر، بوني؛ ووترمان، مايكل س.؛ يو، يون ويليام (يونيو 2021). "مسافة ليفنشتاين، ومقارنة التسلسلات، والبحث في قواعد البيانات البيولوجية" . معاملات IEEE في نظرية المعلومات . 67 (6): 3287-3294 . doi : 10.1109/TIT.2020.2996543 . ISSN 1557-9654 . PMC 8274556 .

[6] فاغنر، روبرت أ.؛ فيشر، مايكل ج. (1974)، "مشكلة تصحيح السلسلة إلى السلسلة"، مجلة ACM ، 21 (1): 168-173 ، doi : 10.1145/321796.321811 ، S2CID 13381535

[7] هيلمكفيست، ستين (26 مارس 2012)، خوارزمية ليفنشتاين سريعة وفعالة من حيث الذاكرة.

[8] هيرشبرغ، د.س. (1975). "خوارزمية فضاء خطي لحساب المتتاليات الفرعية المشتركة القصوى" (ملف PDF) . اتصالات رابطة آلات الحوسبة ( مخطوطة مُقدَّمة). 18 (6): 341-343 . CiteSeerX 10.1.1.348.4774 . doi : 10.1145/360825.360861 . MR 0375829. S2CID 207694727 .

[ssm-9] شولز، كلاوس يو؛ ميهوف، ستويان (2002). "تصحيح سريع للسلاسل النصية باستخدام أوتوماتا ليفنشتاين". المجلة الدولية لتحليل المستندات والتعرف عليها . 5 (1): 67-85 . CiteSeerX 10.1.1.16.652 . doi : 10.1007/s10032-002-0082-8 . S2CID 207046453 .

[10] أندوني، ألكسندر؛ كراوثغامر، روبرت؛ أوناك، كريستوف (2010). تقريب متعدد اللوغاريتمات لمسافة التحرير وتعقيد الاستعلام غير المتماثل . ندوة IEEE حول أسس علوم الحاسوب (FOCS). arXiv : 1005.4033 . Bibcode : 2010arXiv1005.4033A . CiteSeerX : 10.1.1.208.2079 .

[11] أندوني، أ؛ نوساتزكي، ن (2020). مسافة التحرير في زمن شبه خطي: إنه عامل ثابت . ندوة IEEE حول أسس علوم الحاسوب (FOCS). arXiv : 2005.07678 .

[12] باكورس، أرتورس؛ إنديك، بيوتر (2015). لا يمكن حساب مسافة التحرير في وقت شبه تربيعي قوي (إلا إذا كانت SETH خاطئة) . المؤتمر السنوي السابع والأربعون لجمعية ACM حول نظرية الحوسبة (STOC). arXiv : 1412.0348 . Bibcode : 2014arXiv1412.0348B .

[13] وونغ، سي كيه؛ تشاندرا، أشوك كيه. (1976). "حدود مشكلة تحرير السلاسل النصية". مجلة ACM . 23 (1): 13-16 . doi : 10.1145/321921.321923 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[

[ 6 ]

[7]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗