فاصلهٔ Levenshtein کمترین تعدادِ درج، حذف و جایگزینیِ لازم برای تبدیل یک رشته به رشتهٔ دیگر است، وقتی هزینهٔ هر کدام یک باشد. اما عدد۲ به‌تنهایی نمی‌گوید کدام نویسه‌ها عوض شدند. این راهنما جدولِ کامل و والدِ هر خانه را می‌سازد، مسیر را به عقب دنبال می‌کند و برنامهٔ ویرایشِ حاصل را روی خودِ رشته واقعاً اجرا می‌کند؛ خروجیِ تازه، فقط گزارشِ نرخِ خطای متن نیست.
قراردادِ عملیات و واحد را ثابت کنیم
واحدِ این تمرین code point یونیکد است. نگه‌داشتنِ نویسهٔ برابر هزینه۰ و درج، حذف یا جایگزینی هزینه۱ دارند. جابه‌جاییِ دو نویسه یک عملِ مستقلِ یک‌هزینه‌ای نیست؛ بنابراین این فایل الگوریتمِ دارای transposition را اجرا نمی‌کند. نرمال‌سازی، اصلاحِ شکلِ حروف یا تشخیصِ خوشهٔ نویسه هم پنهانی انجام نمی‌شود.
داده‌ها رشته‌های ساخته‌شده‌اند، نه خروجیِ آزمایشِ یک مدلِ گفتار. در نمونهٔ فارسی، «سارا» به «باران» تبدیل می‌شود: س به ب عوض و ن در انتها درج می‌شود؛ هزینه۲ است. این مثالِ ویرایشی، اصلاحِ درستِ نامِ واقعیِ یک شخص یا پیشنهادِ تغییرِ نام نیست.
هر خانهٔ جدول چه می‌گوید؟
d[i][j] فاصلهٔ i نویسهٔ اولِ مبدأ تا j نویسهٔ اولِ مقصد است. ردیفِ مبدأِ خالی هزینهٔ درج‌ها و ستونِ مقصدِ خالی هزینهٔ حذف‌ها را دارد. هر خانه از سه پیشین می‌آید: قطر برای نگه‌داشتن یا جایگزینی، بالا برای حذف و چپ برای درج. هدف کمینه است؛ مقدارِ کوچک‌ترِ هزینه‌ها انتخاب می‌شود.
diagonal = d[i-1][j-1] + (source[i-1] != target[j-1]) delete = d[i-1][j] + 1 insert = d[i][j-1] + 1 d[i][j] = min(diagonal, delete, insert)
هم‌زمان با عدد، پیشینِ انتخاب‌شده و نوعِ عمل را ذخیره می‌کنیم. جدولِ کاملِ نمونهٔ فارسی۵ردیف و۶ستون دارد و همراه فایل است. فقط دو ردیف برای حسابِ عدد کافی می‌تواند باشد، اما نسخهٔ این صفحه برای بازسازیِ ساده، همهٔ جدول و والدها را عمداً نگه می‌دارد.
Traceback را با اجرای ویرایش کامل کنیم
از خانهٔ آخر به والدها برمی‌گردیم تا به شروع برسیم؛ سپس فهرستِ عمل‌ها را برعکس می‌کنیم تا ترتیبِ اجرای مبدأ به مقصد به دست آید. هر عمل، نویسهٔ خوانده‌شده و نوشته‌شده را ثبت می‌کند. برنامه بعداً همین عمل‌ها را روی یک فهرستِ قابل‌ویرایش از مبدأ اجرا می‌کند و متنِ پس از هر گام را در JSON می‌گذارد.
اندیسِ پیشوندِ جدول با مکانِ متغیر در رشتهٔ در حالِ ویرایش یکی نیست. در درج، نویسه‌ای به مکانِ فعلی اضافه و اشاره‌گر جلو می‌رود؛ در حذف، نویسه برداشته می‌شود و اشاره‌گر همان‌جا می‌ماند؛ نگه‌داشتن و جایگزینی هر دو یک خانه جلو می‌روند. پیش از هر عملِ مصرف‌کننده، کد برابر‌بودنِ نویسهٔ واقعی با نویسهٔ مورد انتظار را کنترل می‌کند؛ صرفاً رشتهٔ مقصد را در آخر چاپ نمی‌کند.
یک عددِ بهینه، چند مسیرِ معتبر
برای ab→ba، فاصله۲ است. می‌توان هر دو حرف را جایگزین کرد، یا یکی را حذف و دوباره درج کرد. تابعِ مستقلِ این نمونه همهٔ۱۳مسیرِ هم‌ترازی را می‌شمارد و سه مسیرِ با هزینهٔ کمینه۲ می‌یابد. پس از خودِ عددِ۲، یک برنامهٔ ویرایشِ یکتا نتیجه نمی‌شود.
قاعدهٔ تساویِ فایل روشن است: ابتدا حرکتِ قطریِ نگه‌داشتن یا جایگزینی، سپس حذف و سپس درج. در همین نمونه، دو جایگزینی انتخاب می‌شود. این انتخاب، شاهدِ «قصدِ نویسنده» یا علتِ واقعیِ خطا نیست؛ یک قراردادِ قطعی برای انتخابِ یکی از جواب‌های بهینه است.
| مبدأ→مقصد | فاصله | کنترل مستقلِ تمامِ هم‌ترازی‌ها |
|---|---|---|
| سارا→باران | ۲ | ۶۸۱مسیر؛ یک مسیرِ کمینه |
| ABCD→BCE | ۲ | ۱۲۹مسیر؛ حذف و جایگزینی در جواب |
| ab→ba | ۲ | ۱۳مسیر؛ سه مسیرِ کمینه |
| خالی→آب | ۲ | یک مسیر؛ دو درج |
این کنترل چه چیزی را ثابت نمی‌کند؟
فهرست‌کردنِ همهٔ هم‌ترازی‌ها فقط برای رشته‌های کوچکِ این مثال انجام شده است و روشِ مقیاس‌پذیر نیست. جدولِ معمولِ فاصله با طول‌های n و m حدود n×m کار دارد؛ این اجرای آموزشیِ دارای traceback همان مقدار حافظهٔ جدول را هم مصرف می‌کند. عددِ کم، هم‌معنایی، درستیِ یک مبلغ یا کیفیتِ شنیدنِ صدا را ثابت نمی‌کند.
یِ فارسی و يِ عربی در حالت خام فاصله۱ و دو یِ دقیقاً برابر فاصله۰ دارند؛ سیاستِ همسان‌سازی باید جدا و ازپیش مشخص باشد. برای نرخ‌های ارزیابی به CER و WER فارسی بروید؛ سهمِ این صفحه برنامهٔ ویرایشِ بازسازی‌شده و اجراشده بود. برای تطبیقِ دقیقِ الگو هم KMP مسئلهٔ متفاوتی حل می‌کند.
در درخواستِ اپرانگار، متنِ مرجع و معیارِ خطا را مشخص کنید. هیچ عددِ این نمونه، دقتِ اپرانگار یا نتیجهٔ آزمایشِ سرویس نیست و ویرایشِ حساسِ متن باید با مرجعِ معتبر بررسی شود.
فایل تمرین و منبع
کد کامل Python؛ محاسبه و کنترل‌های مستقل · ورودیِ ساخته‌شده، مراحل و خروجیِ اجرای واقعی
- NIST؛ تعریف کمترینِ درج، حذف و جایگزینی؛ تاریخِ اصلاحِ درج‌شده۱۵مه۲۰۱۹
- MIT 6.006 پاییز۲۰۱۱؛ فقط صفحات۳و۴ دربارهٔ زیرمسئلهٔ دو‌رشته‌ای و سه نوع ویرایش واقعاً دیده شدند؛ در کد هدفِ کمینه طبق تعریف پیاده شده است
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.