کدگذاری فهرست سند با پایتون؛ فاصلهٔ شناسه‌ها و varint کمینه

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

۱. شناسهٔ سند را به فاصله‌های مثبت تبدیل کنیم

در آموزش نمایهٔ معکوس و جست‌وجوی بولی، هر واژه به مجموعه‌ای از سندها متصل می‌شد. مسئلهٔ فعلی پس از تشکیل آن فهرست قرار می‌گیرد: فرض می‌کنیم واژه‌ای در سندهای با شناسهٔ ۳، ۱۳۰، ۱۳۱ و ۱۶۳۸۴ آمده است. این اعداد شناسه‌اند؛ فاصلهٔ زمانی، نشانی بایت یا جایگاه واژه در سند نیستند. روش ذخیرهٔ فاصلهٔ شناسه‌ها در کتاب بازیابی اطلاعات نیز همین جداسازی شناسه و فاصله را توضیح می‌دهد.

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

قرارداد تابع حداکثر شانزده شناسه، هرکدام از یک تا ۴۲۹۴۹۶۷۲۹۵ است. ورودی باید خودِ نوع tuple و عناصر خودِ نوع int پایتون باشند؛ مقدار بولی، اعشاری و رشته پذیرفته نیست. فهرست خالی معتبر است. این کران‌ها انتخاب آموزشی ما هستند و محدودیت ذاتی نمایهٔ معکوس محسوب نمی‌شوند. همچنین شناسه‌های متنیِ آموزش قبلی در این برنامه خودکار به عدد تبدیل نمی‌شوند.

۲. هفت بیت داده و بیتِ ادامه را از قرارداد دیگر جدا کنیم

برای هر فاصله، رقم‌های پایهٔ ۱۲۸ را از کم‌ارزش‌ترین رقم می‌فرستیم. هفت بیت پایینِ هر بایت داده‌اند و بیت بالایی می‌گوید بایت دیگری از همین عدد باقی مانده است: یک یعنی ادامه، صفر یعنی پایان. این جهتِ بیت و ترتیبِ گروه‌ها با توضیح varint در مستندات رسمی Protocol Buffers هماهنگ است؛ ولی برنامهٔ ما فقط فاصله‌های مثبتِ بدون علامت و حداکثر سی‌ودوبیتی را می‌خواند. برچسب فیلد، پیام تودرتو، عدد علامت‌دار و خواندن کامل پیام Protobuf در آن وجود ندارد.

فاصلهٔ ۱۶۲۵۳ برابر ۱۲۵ به‌اضافهٔ ۱۲۶ ضرب‌در ۱۲۸ است. پس بایت اول ۱۲۵ با بیتِ ادامهٔ روشن، یعنی fd شانزده‌شانزدهی، و بایت دوم ۱۲۶، یعنی 7e است. سه فاصلهٔ دیگر هریک در یک بایت جا می‌شوند؛ محمولهٔ کامل ما 03 7f 01 fd 7e است. این رشته، نمایش خوانای پنج بایت است؛ شمار نویسه‌های نمایش شانزده‌شانزدهی را طول دادهٔ دودویی حساب نمی‌کنیم.

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

۳. خوانندهٔ کمینه و محدود را پیش از تحویل نتیجه بسنجیم

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

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

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

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

"""Own bounded canonical postings format; no external codec dependency."""
import itertools
import json
import platform

MAX_ID = (1 << 32) - 1
MAX_DOCS = 16
MAX_BYTES = 5 * MAX_DOCS


def encode_postings(doc_ids):
    """Return immutable bytes for an actual tuple of increasing positive uint32 IDs."""
    if type(doc_ids) is not tuple:
        raise TypeError("doc_ids must be an actual tuple")
    if len(doc_ids) > MAX_DOCS:
        raise ValueError("too many document IDs")
    previous = 0
    # Validate the entire list before producing the private byte buffer.
    for doc_id in doc_ids:
        if type(doc_id) is not int:
            raise TypeError("document IDs must be actual Python ints")
        if not previous < doc_id <= MAX_ID:
            raise ValueError("IDs must be positive, increasing and within uint32")
        previous = doc_id
    output = bytearray()
    previous = 0
    for doc_id in doc_ids:
        remaining = doc_id - previous
        while remaining >= 128:
            output.append((remaining & 127) | 128)
            remaining >>= 7
        output.append(remaining)
        previous = doc_id
    return bytes(output)


def _read_word(data, cursor):
    """Internal uint32 reader; public input bounds are checked by decode_postings."""
    value = 0
    for group in range(5):
        if cursor >= len(data):
            raise ValueError("truncated word")
        byte = data[cursor]
        cursor += 1
        payload = byte & 127
        if group == 4 and (payload > 15 or byte & 128):
            raise ValueError("word exceeds uint32 or five bytes")
        value |= payload << (7 * group)
        if not byte & 128:
            if group and payload == 0:
                raise ValueError("non-minimal word")
            return value, cursor
    raise ValueError("word did not end")


def decode_postings(data):
    """Validate all bytes and return all IDs, or raise without returning a prefix."""
    if type(data) is not bytes:
        raise TypeError("data must be actual bytes")
    if len(data) > MAX_BYTES:
        raise ValueError("payload exceeds the local byte bound")
    decoded = []
    cursor = 0
    previous = 0
    while cursor < len(data):
        gap, cursor = _read_word(data, cursor)
        if gap == 0:
            raise ValueError("zero gap would violate strictly increasing IDs")
        current = previous + gap
        if current > MAX_ID:
            raise ValueError("cumulative document ID exceeds uint32")
        if len(decoded) >= MAX_DOCS:
            raise ValueError("too many document IDs")
        decoded.append(current)
        previous = current
    return tuple(decoded)


def base_digit_reference(digits):
    """Independent arithmetic from supplied least-significant-first base128 digits."""
    if not digits or digits[-1] == 0:
        raise ValueError("positive minimal digit sequence required")
    value = sum(digit * 128 ** place for place, digit in enumerate(digits))
    encoded = bytes(digit + (128 if place + 1 < len(digits) else 0)
                    for place, digit in enumerate(digits))
    return value, encoded


def rejects(function, argument, exception):
    try:
        function(argument)
    except exception:
        return True
    return False


def run_example():
    ids = (3, 130, 131, 16384)
    gaps = tuple(value - previous for previous, value in zip((0,) + ids, ids))
    literal = bytes.fromhex("03 7f 01 fd 7e")
    encoded = encode_postings(ids)
    fixed = b"".join(doc_id.to_bytes(4, "little") for doc_id in ids)
    checks = {}
    checks["hand_gaps_bytes_and_ids"] = (
        gaps == (3, 127, 1, 16253) and encoded == literal
        and decode_postings(literal) == ids)

    oracle_words = []
    choices = (0, 1, 2, 63, 64, 126, 127)
    for length in (1, 2, 3):
        for digits in itertools.product(choices, repeat=length):
            if digits[-1] != 0:
                oracle_words.append(base_digit_reference(digits))
    for low in itertools.product((0, 127), repeat=3):
        for high in (1, 127):
            oracle_words.append(base_digit_reference(low + (high,)))
    for low in itertools.product((0, 127), repeat=4):
        for high in (1, 15):
            oracle_words.append(base_digit_reference(low + (high,)))
    checks["independent_base128_digit_oracle_one_group"] = all(
        encode_postings((value,)) == word and decode_postings(word) == (value,)
        for value, word in oracle_words)

    boundaries = ((127, "7f"), (128, "8001"), (16383, "ff7f"),
                  (16384, "808001"), (MAX_ID, "ffffffff0f"))
    checks["literal_word_boundaries"] = all(
        encode_postings((value,)) == bytes.fromhex(word)
        and decode_postings(bytes.fromhex(word)) == (value,)
        for value, word in boundaries)

    candidates = (1, 2, 127, 128, 16384, MAX_ID)
    subsets = [tuple(value for bit, value in enumerate(candidates) if mask & (1 << bit))
               for mask in range(1 << len(candidates))]
    checks["finite_subset_roundtrips_one_group"] = all(
        decode_postings(encode_postings(values)) == values for values in subsets)
    shifted = tuple(value + 1 for value in ids)
    checks["origin_shift_changes_only_first_gap_for_fixture"] = (
        encode_postings(shifted) == bytes.fromhex("04 7f 01 fd 7e"))
    checks["variable_length_not_always_shorter"] = (
        len(encode_postings((MAX_ID,))) == 5
        and len(MAX_ID.to_bytes(4, "little")) == 4)
    checks["empty_and_document_count_bounds"] = (
        encode_postings(()) == b"" and decode_postings(b"") == ()
        and encode_postings(tuple(range(1, 17))) == bytes([1]) * 16
        and decode_postings(bytes([1]) * 16) == tuple(range(1, 17))
        and rejects(encode_postings, tuple(range(1, 18)), ValueError)
        and rejects(decode_postings, bytes([1]) * 17, ValueError))

    type_bad = ([], (True,), (1.0,), ("1",), (1, False))
    range_bad = ((0,), (-1,), (2, 2), (3, 2), (MAX_ID + 1,), (1, 10 ** 100))
    checks["encoder_exact_types_order_and_range"] = (
        all(rejects(encode_postings, values, TypeError) for values in type_bad)
        and all(rejects(encode_postings, values, ValueError) for values in range_bad))
    checks["decoder_exact_bytes_and_total_length"] = (
        all(rejects(decode_postings, value, TypeError)
            for value in (bytearray([1]), memoryview(b"\x01"), [1], "01"))
        and rejects(decode_postings, bytes([1]) * 81, ValueError))
    checks["truncated_word_rejected"] = all(
        rejects(decode_postings, value, ValueError)
        for value in (b"\x80", b"\x81\x80", b"\x01\x80"))
    checks["non_minimal_words_rejected"] = all(
        rejects(decode_postings, bytes.fromhex(value), ValueError)
        for value in ("8100", "8000", "818000", "ffffffff00"))
    checks["fifth_byte_payload_or_continuation_overflow"] = all(
        rejects(decode_postings, bytes.fromhex(value), ValueError)
        for value in ("ffffffff10", "ffffffff8f", "808080808000"))
    # Even a valid prefix is not delivered by this all-or-error return API.
    bad_tail = bytes.fromhex("037f00")
    preserved = bad_tail[:]
    checks["zero_gap_bad_tail_and_immutable_input"] = (
        rejects(decode_postings, b"\x00", ValueError)
        and rejects(decode_postings, bad_tail, ValueError)
        and bad_tail == preserved)
    checks["cumulative_id_overflow_rejected"] = (
        rejects(decode_postings, bytes.fromhex("ffffffff0f01"), ValueError))
    if not all(type(value) is bool and value for value in checks.values()):
        raise AssertionError(checks)
    return {
        "runtime": {"python": platform.python_version(), "dependencies": "stdlib only"},
        "contract": {"maximum_document_id": MAX_ID, "maximum_documents": MAX_DOCS,
                     "maximum_payload_bytes": MAX_BYTES,
                     "continuation_bit_one_means_more": True,
                     "least_significant_base128_digit_first": True,
                     "minimal_positive_words_only": True,
                     "whole_result_or_exception": True},
        "fixture": {"document_ids": ids, "gaps": gaps,
                    "encoded_hex": encoded.hex(" "), "encoded_bytes": len(encoded),
                    "fixed_uint32_payload_bytes": len(fixed),
                    "decoded_document_ids": decode_postings(encoded)},
        "exercise_answers": {"shifted_ids_encoded_hex": encode_postings(shifted).hex(" "),
                             "overlong_one_hex": "81 00",
                             "single_max_id_hex": encode_postings((MAX_ID,)).hex(" "),
                             "single_max_id_varint_bytes": 5,
                             "single_max_id_fixed_bytes": 4,
                             "max_id_then_gap_one_rejected": True},
        "oracle_word_cases_inside_one_group": len(oracle_words),
        "roundtrip_subsets_inside_one_group": len(subsets),
        "checks": checks, "check_count": len(checks), "all_passed": True,
        "limitations": ["own format, not a full Protobuf or Stanford VB decoder",
                        "no checksum, framing, authentication or corruption guarantee",
                        "byte payload lengths, not RAM or speed measurements",
                        "Python integer range checks, not hardware overflow experiments"]}


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

۴. بایت‌ها را با مرجعِ رقم‌های پایهٔ ۱۲۸ مقایسه کنیم

رفت‌وبرگشتِ کدگذار و خواننده به‌تنهایی کافی نیست؛ دو تابع ممکن است اشتباه مشترکی داشته باشند. مرجع دوم از رقم‌های ازپیش‌انتخاب‌شده آغاز می‌کند، مقدار را با مجموعِ رقم ضرب‌در توانِ ۱۲۸ می‌سازد و بایت را با جمعِ رقم و پرچم ادامه تشکیل می‌دهد. حلقهٔ شیفت و ماسکِ مسیر اصلی را به‌عنوان پاسخ موردانتظار فراخوانی نمی‌کند. نمونهٔ دستیِ پنج‌بایتی نیز تکیه‌گاه جداگانه‌ای برای ترتیب و مرز عددهاست.

اجرای ثبت‌شده با پایتون ۳٫۱۴٫۵ و فقط کتابخانهٔ استاندارد، چهارده گروه آزمونِ نام‌دار را گذرانده است. ۳۹۰ کلمهٔ ساخته‌شده از رقم‌های پایهٔ ۱۲۸ در یک گروه مرجع مستقل سنجیده می‌شوند؛ ۶۴ زیرمجموعهٔ مرتب نیز یک گروهِ رفت‌وبرگشت هستند. این شمارها تعداد حالت‌های محدودند و جای تعداد گروه‌ها یا اثبات همهٔ ورودی‌های ممکن را نمی‌گیرند. مرزهای اندازه، نوع، تعداد، پایانِ کلمه و جمعِ شناسه‌ها جدا بررسی شده‌اند.

{
  "runtime": {
    "python": "3.14.5",
    "dependencies": "stdlib only"
  },
  "contract": {
    "maximum_document_id": 4294967295,
    "maximum_documents": 16,
    "maximum_payload_bytes": 80,
    "continuation_bit_one_means_more": true,
    "least_significant_base128_digit_first": true,
    "minimal_positive_words_only": true,
    "whole_result_or_exception": true
  },
  "fixture": {
    "document_ids": [
      3,
      130,
      131,
      16384
    ],
    "gaps": [
      3,
      127,
      1,
      16253
    ],
    "encoded_hex": "03 7f 01 fd 7e",
    "encoded_bytes": 5,
    "fixed_uint32_payload_bytes": 16,
    "decoded_document_ids": [
      3,
      130,
      131,
      16384
    ]
  },
  "exercise_answers": {
    "shifted_ids_encoded_hex": "04 7f 01 fd 7e",
    "overlong_one_hex": "81 00",
    "single_max_id_hex": "ff ff ff ff 0f",
    "single_max_id_varint_bytes": 5,
    "single_max_id_fixed_bytes": 4,
    "max_id_then_gap_one_rejected": true
  },
  "oracle_word_cases_inside_one_group": 390,
  "roundtrip_subsets_inside_one_group": 64,
  "checks": {
    "hand_gaps_bytes_and_ids": true,
    "independent_base128_digit_oracle_one_group": true,
    "literal_word_boundaries": true,
    "finite_subset_roundtrips_one_group": true,
    "origin_shift_changes_only_first_gap_for_fixture": true,
    "variable_length_not_always_shorter": true,
    "empty_and_document_count_bounds": true,
    "encoder_exact_types_order_and_range": true,
    "decoder_exact_bytes_and_total_length": true,
    "truncated_word_rejected": true,
    "non_minimal_words_rejected": true,
    "fifth_byte_payload_or_continuation_overflow": true,
    "zero_gap_bad_tail_and_immutable_input": true,
    "cumulative_id_overflow_rejected": true
  },
  "check_count": 14,
  "all_passed": true,
  "limitations": [
    "own format, not a full Protobuf or Stanford VB decoder",
    "no checksum, framing, authentication or corruption guarantee",
    "byte payload lengths, not RAM or speed measurements",
    "Python integer range checks, not hardware overflow experiments"
  ]
}

پرسش اول: اگر به همهٔ شناسه‌های مثال یک واحد اضافه کنیم، چه تغییر می‌کند؟ پاسخ: فاصلهٔ نخست چهار می‌شود و بقیه ثابت می‌مانند؛ بایت‌ها 04 7f 01 fd 7e هستند. این نتیجه برای همین مثالِ بدون عبور از مرز طولِ عدد برقرار است.

پرسش دوم: چرا نمایش دو‌بایتیِ یک را قبول نکنیم؟ پاسخ: سیاست کمینهٔ ما آخرین رقم صفر در کلمهٔ چندبایتی را ممنوع کرده است. بنابراین 81 00 با وجود مقدار حسابیِ یک رد می‌شود؛ خواننده آن را خودکار به 01 تبدیل نمی‌کند.

پرسش سوم: آیا یک شناسهٔ تنها همیشه کوتاه‌تر می‌شود؟ پاسخ: بیشینهٔ مجاز با ff ff ff ff 0f پنج بایت می‌خواهد، درحالی‌که نمایش ثابتِ بدون علامتِ سی‌ودوبیتی چهار بایت است. طول متغیر برای هر ورودی برنده نیست.

پرسش چهارم: پس از شناسهٔ بیشینه، فاصلهٔ یک چه نتیجه‌ای دارد؟ پاسخ: جمع از ۴۲۹۴۹۶۷۲۹۵ عبور می‌کند و خواننده کل فراخوانی را رد می‌کند؛ معتبر بودن جداگانهٔ هر کلمه مجوز تحویل فهرست نیست.

۵. طول محموله را مصرف حافظه یا کیفیت جست‌وجو ننامیم

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

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

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

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

• Protocol Buffers؛ رقم‌های پایهٔ ۱۲۸، بیت ادامه و مرزِ پیام کامل
• کتاب بازیابی اطلاعات؛ فاصلهٔ شناسه‌ها در فهرست سند
• کتاب بازیابی اطلاعات؛ قرارداد متفاوتِ پایان عدد در VB

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