پیشنهاد املایی پرس‌وجو با پایتون؛ فاصلهٔ ویرایشی و نامزدهای محدود

وقتی یک واژهٔ پرس‌وجو در واژه‌نامه نیست، می‌توان چند شکلِ نزدیکِ نوشتاری را پیشنهاد کرد؛ اما نباید حدس برنامه را بی‌اعلان جای ورودی کاربر گذاشت. این درس با شش واژهٔ مهندسی، نامزدهای فاصلهٔ ویرایشی را می‌سازد و تساوی پاسخ‌ها را روشن نشان می‌دهد. مثال، غلط‌یاب عمومی فارسی، مدل زبانی یا موتور بازیابی سند نیست؛ فقط یک مرحلهٔ اختیاری برای بررسی پرسشِ بی‌نتیجه است.

۱. فاصلهٔ ویرایشی را از معنای پرس‌وجو جدا کنیم

ورودی دستی moter است و واژه‌نامه، sensor,motor,relay,meter,sender,rotor را دارد. هم موتور و هم متر می‌توانند با یک جایگزینی به شکل ورودی نزدیک شوند. از خود رشته معلوم نیست کاربر کدام را می‌خواسته است؛ زمینهٔ مدار، جمله و هدف کاربر در این داده وجود ندارد.

تعریف Levenshtein در NIST DADS کمترین تعداد درج، حذف و جایگزینی لازم را بیان می‌کند. در قرارداد ما هزینهٔ هرکدام یک و تطابق صفر است. این عدد، احتمال درست‌بودن واژه یا نمرهٔ ارتباط سند نیست. واژه‌ای با فاصلهٔ کمتر هم می‌تواند از نظر موضوع کاملاً نامناسب باشد.

واژه‌نامه صریح و محدود است؛ پیشنهادها فقط از همان فهرست می‌آیند. برنامه واژهٔ تازه تولید نمی‌کند، سندی را از اینترنت پیدا نمی‌کند و از نبود پیشنهاد، نامعتبر بودنِ زبانیِ ورودی را نتیجه نمی‌گیرد. برای نمونه، نبود یک نام قطعهٔ تخصصی در شش واژهٔ ما، دلیلی برای عوض‌کردن آن نام نیست.

۲. درج و حذف و جایگزینی را روی نقاط کد بشماریم

واحد محاسبه، نقطهٔ کد در رشتهٔ پایتون است. مستندات str رشته را دنبالهٔ تغییرناپذیرِ نقاط کد یونیکد معرفی می‌کند. بنابراین یک حرف فارسی می‌تواند یک واحد حساب شود، هرچند نمایش UTF-8 آن چند بایت دارد. طول بایتی را جای طولِ این الگوریتم نمی‌گذاریم.

ضمیمهٔ ۲۹ یونیکد نیز فرق نقطهٔ کد و واحدِ درک‌شدهٔ نوشتاری را توضیح می‌دهد. یک حرف همراه علامت ترکیبی می‌تواند از چند نقطهٔ کد ساخته شود. کد ما مرزبندی گرافیم را پیاده نمی‌کند؛ پس «یک ویرایش» لزوماً یک فشار کلید، یک حرفِ دیداری یا یک اشتباهِ طبیعیِ انسان نیست.

برای نمونه، e + U+0301 دو نقطهٔ کد دارد؛ در برابر شکلِ ازپیش‌ترکیب‌شدهٔ U+00E9، فاصلهٔ خامِ این قرارداد دو است. نرمال‌سازی انجام نمی‌دهیم. درس کلیدهای جست‌وجوی فارسی سیاست متفاوتِ ساخت کلید را جدا بررسی می‌کند؛ آن تغییرها نباید بی‌اعلان داخل فاصلهٔ خام پنهان شوند.

۳. نامزدهای واژه‌نامه را با سقف فاصله مرتب کنیم

شعاع یک یعنی فقط واژه‌هایی را نگه داریم که فاصله‌شان حداکثر یک است. پاسخ نمونه meter و سپس motor است؛ هر دو فاصلهٔ یک دارند. قاعدهٔ تساوی، ترتیب خام رشته‌های پایتون است. این ترتیب را مرتب‌سازی زبانیِ فارسی یا ترجیح معنایی معرفی نمی‌کنیم.

با شعاع دو، rotor با دو جایگزینی اضافه می‌شود و پس از دو نامزدِ یک‌ویرایشی قرار می‌گیرد. اگر سقف تعداد خروجی یک باشد، فقط meter می‌ماند؛ این حذف به قاعدهٔ تساوی مربوط است، نه کشف نیتِ «اندازه‌گیری» در پرسش. افزایش تعداد خروجی نیز نامزدِ خارج از واژه‌نامه را ایجاد نمی‌کند.

تابع فاصله وقتی پاسخ بیش از شعاع باشد، مقدار تهی می‌دهد؛ مقدار تهی را فاصلهٔ واقعیِ رشته‌ها نمی‌نامیم. اختلاف طولِ بزرگ‌تر از شعاع هم بلافاصله رد می‌شود، چون حداقل به همان تعداد درج یا حذف نیاز است. جابه‌جایی دو جزء، عملیات مستقلِ تک‌هزینه نیست؛ ab به ba دو ویرایش می‌خواهد.

۴. کد پویا را با جست‌وجوی مستقل ویرایش‌ها بسنجیم

فایل query_edit_distance.py با Python 3.14.5 و کتابخانهٔ استاندارد اجرا شده است. هر رشته حداکثر بیست‌وچهار نقطهٔ کد دارد و شعاع عدد صحیح صفر تا دو است. رابطِ پیشنهاد، یک واژهٔ ناتهی و بدون فاصلهٔ سفید می‌خواهد؛ رابطِ خودِ فاصله، رشتهٔ تهی را هم برای آزمون درج و حذف می‌پذیرد.

"""Bounded code-point Levenshtein candidates, not a semantic correction system."""
import itertools
import json
import platform
import unicodedata


def _text(value, allow_empty=True):
    if type(value) is not str or len(value) > 24 or (not allow_empty and not value):
        raise ValueError("actual str with at most 24 code points required")
    return value


def _radius(value):
    if type(value) is not int or not 0 <= value <= 2:
        raise ValueError("radius must be an actual integer in 0..2")


def bounded_distance(a, b, radius):
    """Exact Levenshtein distance if <= radius; otherwise None, not a distance."""
    _text(a); _text(b); _radius(radius)
    m, n = len(a), len(b)
    if abs(m - n) > radius:
        return None
    infinity = radius + 1
    previous = [j if j <= radius else infinity for j in range(n + 1)]
    for i in range(1, m + 1):
        current = [infinity] * (n + 1)
        if i <= radius:
            current[0] = i
        for j in range(max(1, i - radius), min(n, i + radius) + 1):
            current[j] = min(previous[j] + 1, current[j - 1] + 1,
                             previous[j - 1] + (a[i - 1] != b[j - 1]))
        previous = current
    return previous[n] if previous[n] <= radius else None


def typo_candidates(query, vocabulary, radius=1, limit=5):
    _text(query, allow_empty=False); _radius(radius)
    if any(c.isspace() for c in query):
        raise ValueError("one query term, no whitespace")
    if type(vocabulary) not in (list, tuple) or len(vocabulary) > 32:
        raise ValueError("bounded explicit vocabulary list/tuple")
    for word in vocabulary:
        _text(word, allow_empty=False)
        if any(c.isspace() for c in word):
            raise ValueError("each vocabulary item is one term")
    if len(set(vocabulary)) != len(vocabulary):
        raise ValueError("duplicate vocabulary entry")
    if type(limit) is not int or not 0 <= limit <= 32:
        raise ValueError("limit must be an actual integer in 0..32")
    candidates = []
    for word in vocabulary:
        distance = bounded_distance(query, word, radius)
        if distance is not None:
            candidates.append({"term": word, "distance": distance})
    candidates.sort(key=lambda row: (row["distance"], row["term"]))
    return candidates[:limit]


def brute_edit_reference(a, b, radius):
    """Independent bounded breadth-first search over literal edited strings.

    Only short binary-alphabet oracle fixtures use this function; it is not the
    implementation used to generate the engineering vocabulary candidates.
    """
    if a == b:
        return 0
    alphabet = sorted(set(a + b))
    frontier = {a}
    seen = {a}
    max_length = max(len(a), len(b)) + radius
    for depth in range(1, radius + 1):
        following = set()
        for word in frontier:
            for i in range(len(word)):
                following.add(word[:i] + word[i + 1:])
                for char in alphabet:
                    following.add(word[:i] + char + word[i + 1:])
            if len(word) < max_length:
                for i in range(len(word) + 1):
                    for char in alphabet:
                        following.add(word[:i] + char + word[i:])
        if b in following:
            return depth
        following -= seen
        seen |= following
        frontier = following
    return None


def _rejects(function):
    try:
        function()
    except ValueError:
        return True
    return False


def run_example():
    vocabulary = ["sensor", "motor", "relay", "meter", "sender", "rotor"]
    one = typo_candidates("moter", vocabulary, 1, 5)
    two = typo_candidates("moter", vocabulary, 2, 5)
    checks = {}
    checks["hand_equal_distance_engineering_candidates"] = one == [{"term": "meter", "distance": 1}, {"term": "motor", "distance": 1}]
    checks["hand_radius_two_adds_rotor_after_ties"] = two == one + [{"term": "rotor", "distance": 2}]
    checks["insertion_deletion_substitution_and_empty_baselines"] = (
        bounded_distance("mot", "motor", 2) == 2 and bounded_distance("motor", "mot", 2) == 2 and
        bounded_distance("meter", "motor", 2) == 2 and bounded_distance("", "ab", 2) == 2 and
        bounded_distance("ab", "", 2) == 2 and bounded_distance("", "", 0) == 0)
    checks["transposition_is_two_edits_not_damerau_one"] = bounded_distance("ab", "ba", 1) is None and bounded_distance("ab", "ba", 2) == 2
    checks["zero_radius_keeps_only_exact_term"] = typo_candidates("motor", vocabulary, 0) == [{"term": "motor", "distance": 0}]
    checks["length_difference_exceeding_radius_rejected"] = bounded_distance("a", "aaaa", 2) is None and bounded_distance("a", "aaa", 2) == 2
    checks["code_point_unit_not_utf8_byte_count"] = len("م".encode("utf-8")) == 2 and bounded_distance("", "م", 1) == 1
    checks["combining_sequence_is_not_canonically_normalized"] = len("e\u0301") == 2 and bounded_distance("e\u0301", "\u00e9", 1) is None and bounded_distance("e\u0301", "\u00e9", 2) == 2
    checks["joiner_and_arabic_persian_letter_distinctions_kept"] = bounded_distance("می\u200cرود", "میرود", 1) == 1 and bounded_distance("ي", "ی", 1) == 1
    checks["vocabulary_permutation_preserves_tie_order"] = typo_candidates("moter", list(reversed(vocabulary)), 1) == one and typo_candidates("moter", vocabulary, 1, 1) == one[:1]
    checks["zero_limit_does_not_bypass_input_validation"] = typo_candidates("moter", vocabulary, 1, 0) == [] and _rejects(lambda: typo_candidates("moter", ["motor", "motor"], 1, 0))
    checks["no_candidate_and_empty_vocabulary_are_explicit"] = typo_candidates("zzzz", vocabulary, 1) == [] and typo_candidates("moter", [], 1) == []
    checks["text_type_length_and_query_word_contract"] = all(_rejects(lambda bad=bad: bounded_distance(bad, "a", 1)) for bad in [b"a", 1, True, "a" * 25]) and all(_rejects(lambda q=q: typo_candidates(q, vocabulary)) for q in ["", "two words", "motor\n"])
    checks["radius_and_limit_integer_bounds"] = all(_rejects(lambda r=r: typo_candidates("moter", vocabulary, r)) for r in [True, -1, 3, 1.0]) and all(_rejects(lambda k=k: typo_candidates("moter", vocabulary, 1, k)) for k in [True, -1, 33, 1.0])
    checks["vocabulary_type_uniqueness_and_term_bounds"] = all(_rejects(lambda words=words: typo_candidates("moter", words)) for words in ["motor", ["motor", "motor"], [""], ["two words"], [1], ["a" * 25], [str(i) for i in range(33)]])
    words = ["".join(chars) for n in range(4) for chars in itertools.product("ab", repeat=n)]
    oracle_ok = True
    oracle_cases = 0
    for a, b, radius in itertools.product(words, words, range(3)):
        oracle_ok &= bounded_distance(a, b, radius) == brute_edit_reference(a, b, radius)
        oracle_cases += 1
    checks["independent_breadth_first_literal_edit_oracle"] = bool(oracle_ok and oracle_cases == 675)
    before = vocabulary.copy()
    typo_candidates("moter", vocabulary, 2)
    checks["caller_vocabulary_not_rewritten_or_mutated"] = vocabulary == before and "moter" not in vocabulary
    assert all(type(v) is bool and v for v in checks.values()), checks
    return {"python": platform.python_version(), "dependencies": {"standard_library_only": True, "python_unicode_database": unicodedata.unidata_version},
            "example": {"query": "moter", "vocabulary": vocabulary, "radius_1_candidates": one,
                        "radius_2_candidates": two, "one_candidate_limit": typo_candidates("moter", vocabulary, 1, 1),
                        "unit": "raw Python str code points", "automatic_query_replacement": False},
            "oracle_cases_inside_one_group": oracle_cases, "checks": checks,
            "limitations": ["Insert/delete/substitute unit cost only, no transposition primitive",
                "No Unicode normalization, case folding, grapheme segmentation, phonetic or semantic model",
                "Bounded explicit vocabulary, no document retrieval, spelling accuracy benchmark or human intent inference"]}


if __name__ == "__main__":
    print(json.dumps(run_example(), ensure_ascii=False, indent=2))

برنامهٔ پویا هزینهٔ پیشوندها را در دو سطر نگه می‌دارد. هر خانه از حذف، درج یا حرکت قطری با هزینهٔ تطابق یا جایگزینی به دست می‌آید. فقط خانه‌های نزدیک قطر، با اختلاف شمارهٔ سطر و ستون حداکثر برابر شعاع، به‌روزرسانی می‌شوند. بااین‌حال بافرهای سطر کامل‌اند؛ ادعای حافظهٔ صرفاً به‌اندازهٔ شعاع یا سرعتِ اندازه‌گیری‌شده نداریم.

مرجع مستقل اصلاً جدولِ هزینه را صدا نمی‌زند. برای رشته‌های خیلی کوتاهِ ساخته‌شده از دو نماد، همهٔ ویرایش‌های ممکن را لایه‌به‌لایه می‌سازد و نخستین لایهٔ رسیدن به هدف را پیدا می‌کند. طول میانی محدود و فضای آزمون کوچک است؛ این جست‌وجوی فراگیر، مسیر عملیِ پیشنهادهای واژه‌نامهٔ اصلی نیست.

هفده گروه بررسی اجرا شده‌اند. پانزده رشتهٔ با طول صفر تا سه، همراه تمام جفت‌ها و سه شعاع، ۶۷۵ مقایسه را داخل یک گروه می‌سازند. پاسخ دستی، تساوی نامزدها، شعاع صفر، نبود نتیجه، اثر علامت ترکیبی و تفاوت بایت و نقطهٔ کد جدا بررسی می‌شوند. چند حالت در یک گروه یا تکرار اجرا، شمار بررسی‌های مستقل را زیاد نمی‌کند.

۵. پیشنهاد املایی را اصلاح قطعی یا فهم فارسی ننامیم

واژه‌نامه حداکثر سی‌ودو مدخل یکتا دارد؛ مدخل تهی، فاصله‌دار یا تکراری رد می‌شود. واژه‌نامهٔ تهی مجاز است و پیشنهاد تهی می‌دهد. حد خروجی از صفر تا سی‌ودو است، اما صفر بودن آن اعتبارسنجیِ ورودی را دور نمی‌زند. ترتیب واژه‌نامه تغییر نمی‌کند و هیچ نامزدی به‌جای پرسش اصلی نوشته نمی‌شود.

{
  "python": "3.14.5",
  "dependencies": {
    "standard_library_only": true,
    "python_unicode_database": "16.0.0"
  },
  "example": {
    "query": "moter",
    "vocabulary": [
      "sensor",
      "motor",
      "relay",
      "meter",
      "sender",
      "rotor"
    ],
    "radius_1_candidates": [
      {
        "term": "meter",
        "distance": 1
      },
      {
        "term": "motor",
        "distance": 1
      }
    ],
    "radius_2_candidates": [
      {
        "term": "meter",
        "distance": 1
      },
      {
        "term": "motor",
        "distance": 1
      },
      {
        "term": "rotor",
        "distance": 2
      }
    ],
    "one_candidate_limit": [
      {
        "term": "meter",
        "distance": 1
      }
    ],
    "unit": "raw Python str code points",
    "automatic_query_replacement": false
  },
  "oracle_cases_inside_one_group": 675,
  "checks": {
    "hand_equal_distance_engineering_candidates": true,
    "hand_radius_two_adds_rotor_after_ties": true,
    "insertion_deletion_substitution_and_empty_baselines": true,
    "transposition_is_two_edits_not_damerau_one": true,
    "zero_radius_keeps_only_exact_term": true,
    "length_difference_exceeding_radius_rejected": true,
    "code_point_unit_not_utf8_byte_count": true,
    "combining_sequence_is_not_canonically_normalized": true,
    "joiner_and_arabic_persian_letter_distinctions_kept": true,
    "vocabulary_permutation_preserves_tie_order": true,
    "zero_limit_does_not_bypass_input_validation": true,
    "no_candidate_and_empty_vocabulary_are_explicit": true,
    "text_type_length_and_query_word_contract": true,
    "radius_and_limit_integer_bounds": true,
    "vocabulary_type_uniqueness_and_term_bounds": true,
    "independent_breadth_first_literal_edit_oracle": true,
    "caller_vocabulary_not_rewritten_or_mutated": true
  },
  "limitations": [
    "Insert/delete/substitute unit cost only, no transposition primitive",
    "No Unicode normalization, case folding, grapheme segmentation, phonetic or semantic model",
    "Bounded explicit vocabulary, no document retrieval, spelling accuracy benchmark or human intent inference"
  ]
}

نمایهٔ معکوس و جست‌وجوی واژه مرحلهٔ دیگری است: اینجا فقط شکل نوشتاریِ نامزد را پیشنهاد می‌کنیم، نه شناسهٔ سند. حتی پس از انتخابِ یک واژه باید قرارداد جست‌وجو، دسترسی و ارتباط نتیجه جدا بررسی شوند. تعداد نامزدِ پیدا‌شده نیز سنجهٔ صحت املایی یا نرخ بازیابیِ محصول نیست.

منابع در ۲۵ مهر ۱۴۰۵ خوانده شدند. مدخل NIST در ۲۰۱۹ اصلاح و صفحه‌اش در ۲۰۲۴ قالب‌بندی شده است؛ این تاریخ‌ها انتشار الگوریتم تازه نیستند. سند یونیکد نسخهٔ 18.0.0 را شرح می‌دهد، اما پایگاه یونیکدِ گزارش‌شدهٔ اجرای پایتون 16.0.0 است؛ قواعد مرزبندیِ نسخهٔ هجده در برنامه اجرا نشده‌اند.

پرسش اول: چرا متر پیش از موتور آمد؟ پاسخ: فاصلهٔ هر دو یک است و قاعدهٔ دوم، ترتیب خام رشته است؛ برنامه معنای جمله یا نیت کاربر را ندیده است.

پرسش دوم: شعاع صفر چه می‌کند؟ پاسخ: فقط تطابق دقیقِ همان رشته را نگه می‌دارد؛ تغییر شکل حرف، نیم‌فاصله یا بزرگی حروف خودکار یکسان نمی‌شود.

پرسش سوم: چرا مقدار تهی، عدد سه نیست؟ پاسخ: فقط می‌گوید فاصله از شعاع مجاز بیشتر است؛ ممکن است سه یا بیشتر باشد و این تابع آن مقدارِ دقیق را گزارش نمی‌کند.

پرسش چهارم: آیا دو نامزدِ درستِ محاسباتی یعنی غلط‌یاب فارسی داریم؟ پاسخ: خیر؛ فقط همین واژه‌نامهٔ کوچک را داریم؛ زمینهٔ زبانی، تلفظ و ارزیابی انسانی نداریم. تنها حداقل ویرایشِ همین رشته‌ها طبق قرارداد محدود آزموده شده است.

منابع و مطالعهٔ بیشتر

• NIST DADS؛ تعریف Levenshtein distance
• Unicode18 UAX29؛ مرز گرافیم و تفاوت آن با نقطهٔ کد
• Python؛ str به‌عنوان دنبالهٔ نقاط کد یونیکد

بررسی منابع: ۲۵ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.