جیاوازیی لێڤنشتاین

جیاوازیی لێڤنشتاین

ماتریکسی جیاوازیی دەستکاری بۆ دوو وشە کە تێچووی جێگۆڕکێ بە ١ و تێچووی سڕینەوە یان زیادکردن بە ٠٫٥ بەکاردێنن
کڵاس	پێوانەکردنی جیاوازیی نێوان دوو زنجیرە

لە تیۆریی زانیاری و زمانەوانی و زانستی کۆمپیوتەر، جیاوازیی لێڤنشتاین پێوەرێکی پێوانی زنجیرەنووسەیە بۆ پێوانەکردنی جیاوازیی نێوان دوو زنجیرە. جیاوازیی لێڤنشتاین لەنێوان دوو وشە کەمترین ژمارەی دەستکارییەکانی نووسەیەکە (وەک زیادکردن، سڕینەوە یان جێگۆڕکێ) کە بۆ گۆڕینی وشەیەک بۆ وشەیەکی تر پێویستە. بە ناوی بیرکاری سۆڤیەت، ڤلادیمیر لێڤنشتاین کراوە کە پێوەرەکەی لە ١٩٦٥ دانا.

لەوانەیە جیاوازیی لێڤنشتاین بە جیاوازیی دەستکاریش ناوی ببرێت، ھەرچەندە ڕەنگە زاراوەکە بۆ خێزانێکی گەورەتر لە پێوەرەکانی پێوانی دەستکاری بەکاربێت.

ناساندن

جیاوازیی لێڤنشتاین لە نێوان دوو زنجیرەنووسەی $a,b$ (بە درێژیی $|a|$ و $|b|$ بە ڕیز) بە $\operatorname {lev} (a,b)$ دیاری دەکرێ کاتێک

$\operatorname {lev} (a,b)={\begin{cases}|a|&{\text{ if }}|b|=0,\\|b|&{\text{ if }}|a|=0,\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}&{\text{ if }}\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$ەم لە زنجیرەنووسەی $x$، بە ژماردن لە سفڕەوە بەکاردێت، کەواتە $\operatorname {head} (x)=x_{0}=x[0]$.

لە ھاوکێشەکە، یەکەم بەشی minimum لەگەڵ سڕینەوە (لە $a$ بۆ $b$) و، دووەم لەگەڵ زیادکردن و سێیەمیش لەگەڵ جێگۆڕکێ دەگونجێ.

ئەم ناساندنە ڕاستەوجۆ لەگەڵ جێبەجێکردنی سادەی گەڕانەوەیی دەگونجێ.

نموونە

بۆ نموونە، جیاوازیی لێڤنشتاین لەنێوان «kitten» و «sitting» بریتییە لە ٣، چونکە ئەم ٣ دەستکارییەی خوارەوە وشەیەک دەکەنە یەکێکی تر، و ھیچ ڕێگایەک نییە بە کەمتر لە ٣ دەستکاری بکرێت:

1. sitten ← kitten (دانانی «s» لە جێگەی «k»)،
2. sittin ← sitten (دانانی «i» لە جێگەی «e»)،
3. sitting ← sittin (زیادکردنی «g» لە کۆتایی).

دەتوانرێت نموونەیەکی سادەی سڕینەوە لە «uninformed» و «uniformed» ببیندرێت کە جیاوازییەکەیان بریتییە لە ١:

1. uniformed ← uninformed (سڕینەوەی «n»).

سنوورەکانی بەرزترین و نزمترین

جیاوازیی لێڤنشتاین چەند ڕێسایەکی سادەی سنوورەکانی بەرزترین و نزمترینی ھەیە کە بەبێ ئەوەی پێویست بە حساباتی تەواو بکات، دەتوانرێت بەرزترین و نزمترین جیاوازیی لێڤنشتاین کە ڕێی تێ دەچێت بزانرێت. ڕێساکان بریتین لە:

• جیاوازییەکە بە لای کەمەوە جیاوازیی درێژییەکەیە.
  • بۆ نموونە، لەنێوان «car» (کە ٣ پیتە) و «cars» (کە ٤ پیتە)، جیاوازییەکە بە لای کەمەوە بریتییە لە ١.
• جیاوازییەکە قەت لە درێژیی وشە درێژەکە زیاتر نییە.
  • بۆ نموونە، بۆ گۆڕینی «run» بۆ «running»، ئەوپەڕی ٧ دەستکاری پێویستە.
• ئەگەر وشەکان ھەمان شت بوون، جیاوازییەکە بریتییە لە سفڕ.
• ژمارەی دەستکارییەکان بۆ گۆڕینی وشەی A ڕاستەوخۆ بۆ C ھەمیشە بچووکتر یان یەکسانە بە سەرجەمی دەستکاریی پێویست بۆ گۆڕینی A بۆ B، و پاشان B بۆ C (لاسەنگەی سێگۆشەیی).
• ئەو وشانە ھەمان درێژییان ھەیە، جیاوازییەکە کەمتر یان یەکسانە بە ژمارەی پییتە نابەرامبەرەکان (کە ئەمە پێی دەڵێن جیاوازیی ھامینگ).
  • بۆ نموونە، بۆ گۆڕینی «flaw» بۆ «lawn»:
    • شوێنی ھەر ٤ پیتەکە گۆڕاوە، بۆیە جیاوازیی ھامینگ بریتییە لە ٤.
    • بەڵام جیاوازیی لێڤنشتاین بریتییە لە ٢ («f» لە سەرەتای وشەکە سڕاوەتەوە و «n» لە کۆتاییی وشەکە زیاد کراوە).

بەکارھێنانەکان

لە نزیککردنەوەی زنجیرەنووسەی چوونیەکدا، مەبەست لە دۆزینەوەی ھاوشێوەکانی زنجیرەنووسە کورتەکانە لە چەندین دەقی درێژتر، لەو حاڵەتانەی کە ژمارەیەکی بچووک لە جیاوازی ڕەچاو دەکرێت. لەوانەیە ئەو زنجیرەنووسە کورتانە، بۆ نموونە، لە فەرھەنگێکەوە بێن. لێرەدا، یەکێک لەو زنجیرەنووسانە بە زۆری کورتە، لەکاتێکدا درێژیی ئەوی تر دەکرێ ھەرچەند بێت. جیاوازیی لێڤنشتاین بوارێکی فراوانی بەکارھێنانی ھەیە، بۆ نموونە لە پشکنەرەکانی ڕێنووس، سیستەمەکانی چاکسازیی ناسینەوەی ھێما بەبینایی، و نەرمامێر تا یارمەتیی وەرگێڕانی زمانی سروشتی بە پشتنبەستن بە بیرگەی وەرگێڕان بدات.

دەکرێ جیاوازیی لێڤنشتاین لەنێوان دوو زنجیرەنووسەی درێژتریش حسابات بکات، بەڵام تێچووی حسابکردنی، کە بە نزیکی لەگەڵ بەرھەمی درێژیی دوو زنجیرەنووسەکە ھاوڕێژەیە، کە ئەمەش وا دەکات بێھوودە بێت. بەم شێوەیە، کە وەک یاریدەدەرێک لە گەڕانی زنجیرەنووسەی نائاشکرا لە بەکارھێنانەکانی وەک ڕیکۆرد لینکەیج بەکار ھات، ئەوا زنجیرەنووسە بەراوردکراوەکان زۆربەی جار کورتن تا یارمەتیی باشترکردنی خێرایی بەراوردکردنەکان بدەن.

لە زمانەوانیدا، جیاوازیی لێڤنشتاین وەک پێوەرێکی پێوان بەکارھاتووە تا جیاوازیی زمانەوانی یان، تا چەند دوو زمان لە یەکتری جیاوازن بپێوێت. ئەمە پەیوەندیدارە بە تێگەیشتنی دووقۆڵی: تا جیاوازیی زمانەوانی بەرزتر بێت، تێگەیشتنی دووقۆڵی نزمتر دەبێت، و تا جیاوازیی زمانەوانی نزمتر بێت، تێگەیشتنی دووقۆڵی بەرزتر دەبێت.

جیاوازیی لێڤنشتاین لە بەکارھێنانەکانی وەک بیستنپێوی، یارمەتیی حسابکردنی دروستی لە تاقیکردنەوەکانی بیستنی کەسێک دەدات. بە پێوانی جیاوازیی نێوان ئەو دەنگەی کە لێ دراوە، و ئەو وەڵامەی کە گوێگرەکە دەیدات بە دەستەوە کار دەکات. دەکرێ سزای ھەر ھەڵەیەک بە دوو ڕێگە چارە بکرێت: یان ھەر ھەڵەیەک تێچوویەکی جێگیری دەدرێتێ، یانیش تێچووەکە کێشدارە، کە سزایەکی بچووکتر دەداتە ئەو ھەڵە دەنگییانە کە زۆر لە یەکتری دەچن.

جیاوازیی لێڤنشتاین و ئەلگۆریتمە ھاوشێوەکانی لە زیندەزانیارییەکان، جیاوازیی نێوان زنجیرە پەیوەندیدارەکان بە ژینناسی وەک ئەوانەی لە دی ئێن ئەی و پرۆتین ھەن دەپێون. ئەو دەستکارییانەی لە ئەلگۆریتمەکە ڕوو دەدەن ھاوشێوەی ئەوانەن کە لە بازدانە بۆماوەیییەکان ڕوو دەدەن: زیادکردن، سڕینەوە یان جێگۆڕکێی نیوکلیۆتاید (لە دی ئێن ئەی) یان ترشی ئەمینی (لە پڕۆتین). کاتێک ژمارەی لێڤنشتاین لە نێوان دوو زنجیرەکە بچووک بێت، ئەوا ئەوە ئاماژەیەکی بەھێزە کە دوو بوونەوەرەکە یان پەیوەندییەکی نزیکیان ھەیە یانیش دوو پارچەکەی دی ئێن ئەی ھەمان کار دەکەن.

پەیوەندی لەگەڵ پێوەرەکانی تری پێوانی جیاوازیی دەستکاری

وتاری سەرەکی: جیاوازیی دەستکاری

جیاوازیی لێڤنشتاین یەکێکە لەو چەندین ڕێگایەی کە جیاوازیی دەستکاری دەپێوێت. ڕێگەکانی تر بەپێی کردەوە تایبەتەکانی دەستکاری کە ھەر یەکەیان ڕێگەی پێ دەدەن جیا دەکرێنەوە. بۆ نموونە:

• جیاوازیی دەمەڕاو–لێڤنشتاین ڕێگە بە ھەمان ئەو دەستکارییانە دەدات کە لێڤنشتاین ڕێگەی پێ دەدات، بەڵام ئەمیان ڕێگە بە ئاڵوگۆڕکردنی دوو نووسەی دراوسێی یەکتریش دەدات.
• جیاوازیی LCS تەنیا ڕێگە بە زیادکردن و سڕینەوە دەدات و ڕێگە بە جێگۆڕکێکردن نادات.
• جیاوازیی ھامینگ تەنیا ڕێگە بە جێگۆڕکێکردن دەدات، و لە ئاکامدا، دەتوانرێت تەنیا لەسەر ئەو زنجیرەنووسانەی کە ھەمان درێژییان ھەیە بەکاربێت.
• جیاوازیی جارۆ تەنیا ڕێگە بە ئاڵوگۆڕکردنی نووسەکان دەدات.

بەگشتی، جیاوازیی دەستکاری بە کردارە ڕێگەپێدراوەکان و تێچووەکانیان پێناسە دەکرێت. ئەم چەمکە بۆ ئەلگۆریتمە پێشکەوتووەکانی ڕێکخستنی زنجیرەییی دی ئێن ئەی وەک ئەلگۆریتمی سمیت–واتەرمان درێژ دەبێتەوە کە دەکرێ تێچووی کردارێک پشت بە شوێنەکەشی لەناوی زنجیرەکەدا ببەستێت.

ئەمانەش ببینە

• ئەپاچی لووسیین (گەڕانچییەکی سەرچاوەکراوە کە جیاوازیی دەستکاری جێبەجێ دەکات)
• بۆشاییی مەتری

بەستەرە دەرەکییەکان

• Black، Paul E.، ed. (١٤ی ئابی ٢٠٠٨)، «Levenshtein distance»، Dictionary of Algorithms and Data Structures [online]، U.S. National Institute of Standards and Technology، لە ٢ی تشرینی دووەمی ٢٠١٦ ھێنراوە
• جێبەجێکردنەکانی ڕۆسێتا کۆد لەسەر جیاوازیی لێڤنشتاین