جست‌وجوی عبارت در پایتون؛ نمایهٔ مکانی، واژهٔ تکراری و رخداد هم‌پوشان

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

۱. حضور واژه‌ها برای تشخیص عبارت کافی نیست

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

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

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

۲. همهٔ جایگاه‌های تکرار را در نمایه نگه داریم

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

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

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

۳. با جابه‌جایی جایگاه‌ها، آغاز مشترک را پیدا کنیم

اگر واژهٔ نخست در جایگاه s و واژهٔ دوم در s+1 باشد، با کم‌کردن یک از جایگاه واژهٔ دوم، هر دو به s می‌رسند. برای واژهٔ سوم دو واحد کم می‌کنیم و همین الگو ادامه دارد. اشتراک این مجموعه‌های جابه‌جاشده، تمام شروع‌های معتبر را می‌دهد. هر محاسبه درون یک شناسهٔ سند انجام می‌شود و جایگاه سندهای مختلف با هم ترکیب نمی‌شود.

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

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

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

فایل positional_phrase_search.py با Python 3.14.5 و کتابخانهٔ استاندارد اجرا شده است. در D3 سه واژهٔ الف پشت سر هم داریم. عبارت «الف الف» از صفر و یک آغاز می‌شود؛ رخدادها هم‌پوشانی دارند و هر دو گزارش می‌شوند. برای سه الفِ پرسش، فقط شروع صفر می‌ماند. شمارش غیرهم‌پوشان، مسئلهٔ دیگری است و قرارداد این تابع نیست.

"""Exact adjacent token phrases in a tiny synthetic positional index.

No text analyzer, synonym graph, slop, ranking, database or search service.
"""
from copy import deepcopy
from itertools import product
import json
import platform
import re


def token_list(value, minimum, maximum, error):
    if (type(value) is not list or not minimum <= len(value) <= maximum
            or any(type(t) is not str or not 1 <= len(t) <= 24
                   or any(c.isspace() for c in t) for t in value)):
        raise ValueError(error)
    return tuple(value)


def make_index(documents):
    if type(documents) is not dict or len(documents) > 8:
        raise ValueError('documents')
    postings = {}
    for doc_id in sorted(documents, key=str):
        if type(doc_id) is not str or re.fullmatch(r'[A-Za-z][A-Za-z0-9_]{0,15}', doc_id, re.ASCII) is None:
            raise ValueError('document_id')
        tokens = token_list(documents[doc_id], 0, 64, 'document_tokens')
        for position, token in enumerate(tokens):
            postings.setdefault(token, {}).setdefault(doc_id, []).append(position)
    return {token: {doc: tuple(positions) for doc, positions in docs.items()}
            for token, docs in postings.items()}


def phrase_occurrences(index, phrase):
    """index must be produced by make_index; arbitrary index objects not parsed."""
    phrase = token_list(phrase, 1, 8, 'phrase')
    first = index.get(phrase[0], {})
    results = {}
    for doc_id in sorted(first):
        starts = set(first[doc_id])
        for offset, token in enumerate(phrase[1:], 1):
            positions = index.get(token, {}).get(doc_id, ())
            starts.intersection_update(position - offset for position in positions)
            if not starts:
                break
        if starts:
            results[doc_id] = sorted(starts)
    return results


def sliding_oracle(documents, phrase):
    """Independent direct contiguous sequence comparison, without any postings."""
    matches = {}
    for doc_id, words in documents.items():
        starts = []
        for start in range(len(words) - len(phrase) + 1):
            if words[start:start + len(phrase)] == phrase:
                starts.append(start)
        if starts:
            matches[doc_id] = starts
    return matches


def rejected(call, message):
    try:
        call()
    except ValueError as error:
        return str(error) == message
    return False


def run_example():
    documents = {
      'D1': ['جریان', 'موتور', 'کم', 'است', 'جریان', 'موتور'],
      'D2': ['جریان', 'زیاد', 'موتور'],
      'D3': ['الف', 'الف', 'الف'], 'D4': [],
      'D5': ['جریان'], 'D6': ['موتور']}
    before = deepcopy(documents)
    index = make_index(documents)
    query = ['جریان', 'موتور']
    before_query = list(query)
    matches = phrase_occurrences(index, query)
    and_docs = sorted(set(index['جریان']) & set(index['موتور']))
    repeated = phrase_occurrences(index, ['الف', 'الف'])
    exact_literals = make_index({'D': ['می\u200cرود', 'کم،']})
    snapshot = deepcopy(index)
    copied_source = deepcopy(documents)
    detached = make_index(copied_source)
    copied_source['D1'][0] = 'changed'
    oracle_cases, oracle_ok = 0, True
    for length in range(6):
        for sequence in product(['الف', 'ب'], repeat=length):
            corpus = {'D': list(sequence)}
            positions = make_index(corpus)
            for query_length in range(1, 4):
                for phrase in product(['الف', 'ب'], repeat=query_length):
                    wanted = list(phrase)
                    oracle_ok &= phrase_occurrences(positions, wanted) == sliding_oracle(corpus, wanted)
                    oracle_cases += 1
    maximum_index = make_index({'D': ['الف'] * 64})
    checks = {
      'hand_all_positions_preserved': index['جریان'] == {'D1': (0, 4), 'D2': (0,), 'D5': (0,)} and index['موتور'] == {'D1': (1, 5), 'D2': (2,), 'D6': (0,)},
      'hand_adjacent_phrase_starts': matches == {'D1': [0, 4]},
      'and_presence_is_not_adjacency': and_docs == ['D1', 'D2'] and sorted(matches) == ['D1'],
      'repeated_term_overlapping_occurrences': repeated == {'D3': [0, 1]},
      'triple_repeated_term_has_one_start': phrase_occurrences(index, ['الف'] * 3) == {'D3': [0]},
      'one_token_query_returns_every_occurrence': phrase_occurrences(index, ['جریان']) == {'D1': [0, 4], 'D2': [0], 'D5': [0]},
      'unknown_term_and_empty_index_return_no_match': phrase_occurrences(index, ['ناموجود']) == {} and phrase_occurrences(make_index({}), ['الف']) == {},
      'reversed_or_gapped_terms_not_exact_phrase': phrase_occurrences(index, ['موتور', 'جریان']) == {} and phrase_occurrences(make_index({'D': documents['D2']}), query) == {},
      'no_phrase_across_document_boundaries': phrase_occurrences(make_index({'D5': ['جریان'], 'D6': ['موتور']}), query) == {},
      'zwnj_and_punctuation_remain_exact_literals': phrase_occurrences(exact_literals, ['می\u200cرود']) == {'D': [0]} and phrase_occurrences(exact_literals, ['می', 'رود']) == {} and phrase_occurrences(exact_literals, ['کم']) == {},
      'source_query_and_index_not_mutated': documents == before and query == before_query and index == snapshot,
      'document_order_and_source_alias_do_not_change_matches': phrase_occurrences(make_index(dict(reversed(list(documents.items())))), query) == matches and phrase_occurrences(detached, query) == matches,
      'phrase_container_and_length_contracts': all(rejected(lambda value=value: phrase_occurrences(index, value), 'phrase') for value in ['الف ب', [], ['الف'] * 9, ('الف',)]),
      'corpus_container_identifier_and_count_contracts': rejected(lambda: make_index([]), 'documents') and rejected(lambda: make_index({'A' + str(i): [] for i in range(9)}), 'documents') and all(rejected(lambda value=value: make_index({value: []}), 'document_id') for value in [True, 'D/1', 'A' * 17]),
      'invalid_token_type_whitespace_and_size_reject': all(rejected(lambda value=value: make_index({'D': [value]}), 'document_tokens') and rejected(lambda value=value: phrase_occurrences(index, [value]), 'phrase') for value in ['', 1, True, 'الف ب', 'الف\tب', 'x' * 25]),
      'query_longer_than_document_has_no_occurrence': phrase_occurrences(index, ['الف'] * 4) == {} and phrase_occurrences(make_index({'D': []}), ['الف']) == {},
      'independent_exhaustive_sliding_window_oracle': oracle_cases == 882 and bool(oracle_ok),
      'maximum_bounds_and_last_legal_start': phrase_occurrences(maximum_index, ['الف'] * 8) == {'D': list(range(57))} and phrase_occurrences(make_index({'D': ['x' * 24]}), ['x' * 24]) == {'D': [0]} and rejected(lambda: make_index({'D': ['الف'] * 65}), 'document_tokens'),
    }
    assert len(checks) == 18 and all(type(value) is bool and value for value in checks.values()), checks
    return {'python': platform.python_version(), 'dependencies': 'Python standard library only',
            'scope': 'Exact adjacent pretokenized synthetic words only; no analyzer, normalization, Lucene execution, relevance or production search claim',
            'results': {'documents': documents, 'phrase': query, 'phrase_start_positions': matches,
                        'and_candidate_documents': and_docs, 'repeated_phrase_start_positions': repeated,
                        'positions_unit': 'Zero-based token index within each document, not character/byte offset',
                        'oracle_cases_inside_one_group': oracle_cases}, 'checks': checks}


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

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

{
  "python": "3.14.5",
  "dependencies": "Python standard library only",
  "scope": "Exact adjacent pretokenized synthetic words only; no analyzer, normalization, Lucene execution, relevance or production search claim",
  "results": {
    "documents": {
      "D1": [
        "جریان",
        "موتور",
        "کم",
        "است",
        "جریان",
        "موتور"
      ],
      "D2": [
        "جریان",
        "زیاد",
        "موتور"
      ],
      "D3": [
        "الف",
        "الف",
        "الف"
      ],
      "D4": [],
      "D5": [
        "جریان"
      ],
      "D6": [
        "موتور"
      ]
    },
    "phrase": [
      "جریان",
      "موتور"
    ],
    "phrase_start_positions": {
      "D1": [
        0,
        4
      ]
    },
    "and_candidate_documents": [
      "D1",
      "D2"
    ],
    "repeated_phrase_start_positions": {
      "D3": [
        0,
        1
      ]
    },
    "positions_unit": "Zero-based token index within each document, not character/byte offset",
    "oracle_cases_inside_one_group": 882
  },
  "checks": {
    "hand_all_positions_preserved": true,
    "hand_adjacent_phrase_starts": true,
    "and_presence_is_not_adjacency": true,
    "repeated_term_overlapping_occurrences": true,
    "triple_repeated_term_has_one_start": true,
    "one_token_query_returns_every_occurrence": true,
    "unknown_term_and_empty_index_return_no_match": true,
    "reversed_or_gapped_terms_not_exact_phrase": true,
    "no_phrase_across_document_boundaries": true,
    "zwnj_and_punctuation_remain_exact_literals": true,
    "source_query_and_index_not_mutated": true,
    "document_order_and_source_alias_do_not_change_matches": true,
    "phrase_container_and_length_contracts": true,
    "corpus_container_identifier_and_count_contracts": true,
    "invalid_token_type_whitespace_and_size_reject": true,
    "query_longer_than_document_has_no_occurrence": true,
    "independent_exhaustive_sliding_window_oracle": true,
    "maximum_bounds_and_last_legal_start": true
  }
}

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

۵. مرز تحلیل واژه و چهار پرسش پاسخ‌دار

مستندات match_phrase در Elasticsearch نقش تحلیل‌گر و پارامتر slop را جدا می‌کند. کد ما فقط مجاورت دقیق دارد و slop قابل تنظیم ندارد. «کم» با «کم،» و «می‌رود» با دو واژهٔ «می رود» برابر نیستند. برای تغییر این رفتار باید سیاستی مانند نرمال‌سازی فارسی را مستقل تعریف و اثر آن را بر جایگاه‌ها بررسی کرد.

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

پرسش دوم: چرا تکرار الف را به یک واژه کاهش نمی‌دهیم؟ پاسخ: چون «الف» و «الف الف» دو پرسش متفاوت‌اند. پرسش دوم دو رخداد مجاور می‌خواهد؛ حذف تکرار، شرط مورد جست‌وجو را تغییر می‌دهد.

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

پرسش چهارم: آیا نتیجه می‌گوید بهترین سندِ معنایی کدام است؟ پاسخ: خیر؛ فقط محل وقوع دنباله را می‌دهد و رتبه، مجوز یا اعتبار علمی را نمی‌سنجد. منابع در ۲۴ مهر ۱۴۰۵ خوانده شدند؛ Lucene مرجع نسخهٔ 10.3.1 است و هیچ سرویس آن اجرا نشده است. این آموزش پایه، خبر تازه یا ادعای بهبود محصول نیست.

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

• Apache Lucene10.3.1؛ PhraseQuery و موقعیت واژه‌ها
• Elasticsearch؛ match_phrase، تحلیل‌گر و فاصلهٔ slop

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