فهرست مقاله
فرض کنیم متنِ ثابتِ یک گزارش را نگه داشته‌ایم و قرار است چند بار، رشته‌های متفاوت را در آن پیدا کنیم. این بار به جای ساختنِ حالت برای الگو، جایگاهِ آغازِ پسوندهای متن را مرتب می‌کنیم. نتیجه، نمایه‌ای است که یک پرسش را به بازه‌ای پیوسته از پسوندها می‌برد. متنِ مثال تألیفی است و به گزارش یا نمایهٔ واقعیِ سازمان متصل نیست.
۱. متنِ ثابت را با جایگاهِ پسوندها نمایه کنیم
پسوندِ آغازشونده در جایگاهِ سه، تمامِ رشته از همان جایگاه تا پایان است. اگر متن هشت نقطهٔ کد داشته باشد، هشت پسوندِ ناتهی می‌سازیم؛ پسوندِ تهی را وارد نمی‌کنیم. آرایهٔ پسوند در این درس، خودِ رشته‌ها نیست، بلکه جایگشتِ جایگاه‌های شروعِ صفرمبناست. متن کنارِ این جایگشت باقی می‌ماند تا مقایسه و بازسازیِ برش امکان‌پذیر باشد.
فصلِ آرایهٔ پسوند در کتابِ الگوریتم‌های پرینستون، مرتب‌سازیِ پسوندها و جست‌وجوی دودوییِ رشته در این ترتیب را معرفی می‌کند. کدِ حاضر، ساختِ ساده و آموزشی با برشِ رشته را انتخاب کرده است؛ الگوریتمِ بهینهٔ ساختِ آرایه، آرایهٔ پیشوندِ مشترک یا تبدیلِ فشرده‌سازی را پیاده نمی‌کند. ادعای حافظه یا سرعتِ نسخه‌های مرجع را به این برنامه منتقل نمی‌کنیم.
در درسِ جست‌وجوی قطعه‌ای با KMP، الگو ثابت بود و متن می‌توانست قطعه‌قطعه برسد. اینجا متن پیشاپیش کامل و ثابت است و پرسش عوض می‌شود. افزودنِ متنِ تازه، نمایهٔ قبلی را خودکار به‌روز نمی‌کند؛ باید برای متنِ جدید دوباره بسازیم. این تفاوت، انتخابِ ساختار داده را به شکلِ مصرفِ داده وابسته می‌کند.
سازنده فقط str واقعی می‌پذیرد و متنِ تهی مجاز است. محدودیتِ عددیِ ساختگی برای طول نگذاشته‌ایم، اما ساخت با کلیدِ برشی، حافظه و زمان مصرف می‌کند؛ برای متن‌های بزرگ راهکارِ اجراییِ توصیه‌شده‌ای ارائه نشده است. شیء خروجی frozen و جایگاه‌ها tuple هستند. نمونه باید از build ساخته شود؛ ساختِ دستیِ شیء با جایگشتِ نامعتبر خارج از قراردادِ درس است.
۲. ترتیبِ پسوند و ترتیبِ رخداد را جدا نگه داریم
متنِ دستی cabcabca است. ترتیبِ جایگاه‌های پسوند، هفت، چهار، یک، پنج، دو، شش، سه و صفر می‌شود. سه پسوندِ اول با a آغاز می‌شوند و پسوندِ کوتاه‌تر پیش از ادامه‌هایش قرار می‌گیرد. این اعداد رتبهٔ اهمیتِ سند نیستند؛ هر عدد فقط نشانیِ آغازِ یک پسوند در متنِ اصلی است.
برای پرسش cab، دو پسوندِ رتبهٔ شش و هفت مناسب‌اند. برشِ آرایه، جایگاه‌های سه و صفر را به همین ترتیب تحویل می‌دهد. اگر مخاطب، رخدادها را در ترتیبِ خواندنِ متن بخواهد، نتیجه باید صفر و سه باشد. تابع positions این مرتب‌سازیِ عددی را صریح انجام می‌دهد؛ بنابراین ترتیبِ نمایه و ترتیبِ خروجی دو تصمیمِ جدا هستند.
قراردادِ مقایسهٔ رشته در پایتون، ترتیب را بر پایهٔ مقدارِ عددیِ نقاطِ کدِ یونیکد تعریف می‌کند. این ترتیب، ترتیبِ الفباییِ فارسی با قواعدِ زبانی نیست. کد هیچ نویسه‌ای را عوض، حذف یا هم‌ارز نمی‌کند. متن و پرسش با همان توالیِ خام مقایسه می‌شوند و واحدِ جایگاه نیز نقطهٔ کد است.
در شاهدِ یونیکد، یک شکلک، یک علامتِ ترکیبی، صفرِ درونِ رشته و دو شکلِ متفاوتِ ی وجود دارد. طولِ متن هشت نقطهٔ کد و هفده بایتِ UTF-8 است. شکلک در جایگاه‌های یک و پنج دیده می‌شود؛ é با e و علامتِ ترکیبی یکی نیست. پس offset این نمایه را نباید بدون نگاشتِ جدا به بایت، ستونِ نمایش یا خوشهٔ نوشتاری تبدیل کرد.
۳. دو مرزِ دودویی برای پیشوند پیدا کنیم
برابر بودنِ کلِ پسوند با پرسش شرطِ مناسبی نیست: cabca هم رخدادِ cab را نشان می‌دهد. مقایسه‌گر تا طولِ پرسش جلو می‌رود؛ اگر همهٔ نویسه‌های پرسش برابر باشند، صفر برمی‌گرداند، حتی اگر پسوند ادامه داشته باشد. اگر پسوند زودتر تمام شود، کوچک‌تر است. در نخستین نویسهٔ متفاوت، همان ترتیبِ خامِ رشته تعیین‌کننده خواهد بود.
در آرایهٔ مرتب، پاسخِ این مقایسه‌گر ابتدا منفی، سپس صفر و بعد مثبت است؛ ممکن است هر بخش تهی باشد. دلیلِ پیوستگی آن است که تمامِ رشته‌های دارای یک پیشوند، در ترتیبِ لغوی کنارِ هم قرار می‌گیرند. جست‌وجوی اول نخستین پاسخِ نامنفی و جست‌وجوی دوم نخستین پاسخِ مثبت را می‌یابد. بازهٔ نیمه‌بازِ حاصل شامل تمام و فقط پسوندهای مطابق است.
مستندات رسمیِ bisect، فرقِ مرزِ چپ و راست را با شرطِ تقسیمِ ناحیه توضیح می‌دهد. ما همان ایدهٔ مرز را برای مقایسهٔ پیشوند می‌نویسیم و خودِ ماژول را فراخوانی نمی‌کنیم. استفاده از مرزِ راستِ برابریِ کلِ رشته، به‌تنهایی کافی نیست؛ تعریفِ برابری باید واقعاً «پرسش پیشوندِ پسوند است» باشد.
در متنِ دستی، بازهٔ cab برابرِ [6,8) است؛ عددِ هشت عضوِ بازه نیست. پرسشی کوچک‌تر از همهٔ آغازها بازهٔ [0,0) دارد و پرسشی بزرگ‌تر از همه بازهٔ [8,8). برای پرسشِ تهی خطا می‌دهیم، چون معنای «همهٔ مرزهای متن» با نمایه‌ای که پسوندِ تهی ندارد سازگارِ خودکار نیست. این یک سیاستِ رابط است، نه حکمی دربارهٔ همهٔ ابزارهای جست‌وجو.
۴. نمایه را با پیمایشِ مستقیمِ مستقل بسنجیم
کدِ کامل با Python 3.14.5 و فقط کتابخانهٔ استاندارد اجرا شده است. مرجعِ مستقل، تمامِ پنجره‌های کاملِ هم‌اندازهٔ پرسش را مستقیم از متن می‌بُرد و برابر بودن را می‌سنجد. این مرجع نه آرایهٔ پسوند می‌سازد، نه مقایسه‌گرِ پیشوند را صدا می‌زند و نه از دو جست‌وجوی دودویی برای پاسخ استفاده می‌کند.
"""Educational suffix array; raw Unicode codepoint offsets, no normalization."""
from dataclasses import dataclass
from itertools import product
import json
import platform
@dataclass(frozen=True)
class SuffixIndex:
text: str
starts: tuple[int, ...]
@classmethod
def build(cls, text):
if type(text) is not str:
raise TypeError('text must be an actual str')
# Slow, deliberately explicit teaching construction; no empty suffix.
starts = tuple(sorted(range(len(text)), key=lambda i: text[i:]))
return cls(text, starts)
def _compare_prefix(self, start, query):
for offset, char in enumerate(query):
pos = start + offset
if pos == len(self.text):
return -1
current = self.text[pos]
if current < char:
return -1
if current > char:
return 1
return 0 # query is a prefix, even when suffix continues
def interval(self, query):
if type(query) is not str:
raise TypeError('query must be an actual str')
if not query:
raise ValueError('empty query is outside this contract')
lo, hi = 0, len(self.starts)
while lo < hi:
mid = (lo + hi) // 2
if self._compare_prefix(self.starts[mid], query) < 0:
lo = mid + 1
else:
hi = mid
left = lo
hi = len(self.starts)
while lo < hi:
mid = (lo + hi) // 2
if self._compare_prefix(self.starts[mid], query) <= 0:
lo = mid + 1
else:
hi = mid
return left, lo
def positions(self, query):
left, right = self.interval(query)
return tuple(sorted(self.starts[left:right]))
def direct_scan(text, query):
# Independent oracle: inspect every possible complete window, no suffix sort,
# binary search, index data or prefix comparator.
return tuple(i for i in range(len(text) - len(query) + 1)
if text[i:i + len(query)] == query)
def rejects(exception, function, *args):
try:
function(*args)
except exception:
return True
return False
def run():
index = SuffixIndex.build('cabcabca')
checks = {}
checks['literal_suffix_order'] = index.starts == (7, 4, 1, 5, 2, 6, 3, 0)
checks['literal_prefix_interval'] = index.interval('cab') == (6, 8)
checks['rank_order_vs_position_order'] = (index.starts[6:8] == (3, 0)
and index.positions('cab') == (0, 3))
checks['overlap_retained'] = SuffixIndex.build('aaaaa').positions('aaa') == (0, 1, 2)
checks['exact_suffix_and_full_text'] = (index.positions('ca') == (0, 3, 6)
and index.positions(index.text) == (0,))
checks['short_suffix_not_false_match'] = index.positions('cabcabcaa') == ()
checks['absent_extreme_insertions'] = (index.interval('\0') == (0, 0)
and index.interval(chr(0x10ffff)) == (8, 8))
checks['empty_text_and_query_policy'] = (SuffixIndex.build('').interval('x') == (0, 0)
and rejects(ValueError, index.positions, '')
and rejects(ValueError, SuffixIndex.build('').positions, ''))
raw = 'A\U0001f642e\u0301\0\U0001f642یي'
raw_index = SuffixIndex.build(raw)
checks['codepoints_not_bytes_or_graphemes'] = (len(raw) == 8
and raw_index.positions('\U0001f642') == (1, 5)
and raw_index.positions('e\u0301') == (2,)
and raw_index.positions('é') == ()
and raw_index.positions('ی') == (6,)
and raw_index.positions('ي') == (7,))
checks['embedded_zero_and_max_codepoint'] = (raw_index.positions('\0') == (4,)
and SuffixIndex.build(chr(0x10ffff)*2).positions(chr(0x10ffff)) == (0, 1))
checks['invalid_input_types'] = all(rejects(TypeError, SuffixIndex.build, x)
and rejects(TypeError, index.positions, x) for x in (None, b'cab', 3, True, ['c']))
before = (index.text, index.starts)
checks['repeated_queries_preserve_index'] = (index.positions('cab') == index.positions('cab')
and (index.text, index.starts) == before)
cases = 0
all_ok = True
for n in range(7):
for letters in product('ab', repeat=n):
text = ''.join(letters)
candidate = SuffixIndex.build(text)
for m in range(1, 5):
for pattern in product('ab', repeat=m):
query = ''.join(pattern)
got = candidate.positions(query)
expected = direct_scan(text, query)
left, right = candidate.interval(query)
# independent partition witness based on actual fixed windows
windows = [text[i:i+m] for i in candidate.starts]
partition = (all(x < query for x in windows[:left])
and all(x == query for x in windows[left:right])
and all(x > query for x in windows[right:]))
all_ok = all_ok and got == expected and partition
cases += 1
checks['exhaustive_direct_scan_and_partition_ONE_group'] = all_ok and cases == 3810
unicode_pairs = [('الف\U0001f642الف', 'الف'), ('a\0a\0', '\0a'),
('e\u0301ée\u0301', 'e\u0301'), ('یيی', 'ی'),
('\U0010ffffx\U0010ffff', '\U0010ffff')]
checks['independent_unicode_windows'] = all(SuffixIndex.build(t).positions(q) == direct_scan(t, q)
for t, q in unicode_pairs)
assert all(type(v) is bool and v for v in checks.values()), checks
return {'python': platform.python_version(), 'dependencies': 'standard library only',
'text': index.text, 'suffix_array': index.starts,
'query': 'cab', 'suffix_rank_interval': index.interval('cab'),
'positions_in_text_order': index.positions('cab'),
'overlapping_aaa_in_aaaaa': SuffixIndex.build('aaaaa').positions('aaa'),
'unicode_text_codepoints': len(raw), 'unicode_utf8_bytes': len(raw.encode('utf-8')),
'exhaustive_cases_inside_one_group': cases, 'checks': checks}
if __name__ == '__main__':
print(json.dumps(run(), ensure_ascii=False, indent=2))
تمامِ ۱۲۷ متنِ دودویی با طولِ صفر تا شش و تمامِ سی پرسشِ دودویی با طولِ یک تا چهار بررسی شده‌اند. در مجموع، ۳۸۱۰ زوج در یک گروهِ آزمون قرار دارند. افزون بر پاسخِ مستقیم، شرطِ تقسیم نیز کنترل می‌شود: پنجره‌های قبل از چپ کوچک‌تر، داخلِ بازه برابر و پس از راست بزرگ‌تر از پرسش‌اند.
این پنجره‌ها در آزمون از برشِ مستقیم ساخته می‌شوند و از تابعِ مقایسهٔ برنامه کمک نمی‌گیرند. شاهدهای جدا، پسوندِ کوتاه، پرسشِ بلندتر از متن، صفرِ درونی، بیشترین نقطهٔ کد، هم‌پوشانی و ردِ نوعِ ورودی را می‌سنجند. تکرارِ پرسش نیز نباید متن و جایگشتِ نمایه را تغییر بدهد؛ جست‌وجو عملیاتِ ویرایش نیست.
{
"python": "3.14.5",
"dependencies": "standard library only",
"text": "cabcabca",
"suffix_array": [
7,
4,
1,
5,
2,
6,
3,
0
],
"query": "cab",
"suffix_rank_interval": [
6,
8
],
"positions_in_text_order": [
0,
3
],
"overlapping_aaa_in_aaaaa": [
0,
1,
2
],
"unicode_text_codepoints": 8,
"unicode_utf8_bytes": 17,
"exhaustive_cases_inside_one_group": 3810,
"checks": {
"literal_suffix_order": true,
"literal_prefix_interval": true,
"rank_order_vs_position_order": true,
"overlap_retained": true,
"exact_suffix_and_full_text": true,
"short_suffix_not_false_match": true,
"absent_extreme_insertions": true,
"empty_text_and_query_policy": true,
"codepoints_not_bytes_or_graphemes": true,
"embedded_zero_and_max_codepoint": true,
"invalid_input_types": true,
"repeated_queries_preserve_index": true,
"exhaustive_direct_scan_and_partition_ONE_group": true,
"independent_unicode_windows": true
}
}چهارده گروهِ نام‌دار موفق شدند. تعدادِ زوج‌های پیمایش، تعدادِ گروه‌ها را زیاد نمی‌کند و آزمایشِ محدود جایِ اثباتِ همهٔ ورودی‌ها را نمی‌گیرد. هیچ زمان‌سنجی، مقایسه با پایگاهِ داده یا آزمایشِ متنِ بزرگ انجام نشده است. خروجی، فهرستِ رخدادِ دقیق است؛ قطعه‌بندیِ سند، امتیازِ ارتباط و انتخابِ نتیجهٔ مناسب به قراردادهای دیگری نیاز دارند.
۵. چهار پرسش دربارهٔ مرز، هم‌پوشانی و یونیکد
پرسش اول: چرا برای cabcabca و cab، بازهٔ رتبه از شش شروع می‌شود ولی اولین رخداد صفر است؟ پاسخ: رتبه، نشانی در آرایهٔ مرتب است؛ مقدارِ ذخیره‌شده، جایگاهِ متن است. برشِ رتبه‌های شش و هفت، مقادیرِ سه و صفر را می‌دهد و مرتب‌سازیِ عددی آن‌ها ترتیبِ رخداد را می‌سازد. یکی گرفتنِ این دو فضا، نشانیِ نادرست تولید می‌کند.
پرسش دوم: آیا aaa در aaaaa یک بار پیدا می‌شود؟ پاسخ: سه بار، با آغازهای صفر، یک و دو. هر پسوند مستقل بررسی می‌شود و هیچ قاعده‌ای برای حذفِ هم‌پوشانی نداریم. در درسِ جست‌وجوی چندالگوییِ Aho–Corasick نیز معنای «همهٔ رخدادها» مهم بود؛ اینجا همان سیاستِ گزارش را با نمایه‌کردنِ متنِ ثابت بررسی می‌کنیم.
پرسش سوم: می‌توان برای مرزِ راست، نویسه‌ای بسیار بزرگ به پرسش افزود؟ پاسخ: این میان‌بُر قراردادِ امنی برای تمامِ رشته‌های خام نیست؛ متن می‌تواند همان بیشترین نقطهٔ کد را داشته باشد و پرسش نیز می‌تواند به آن ختم شود. مقایسهٔ پیشوند و مرزِ نخستین پاسخِ مثبت، به نشانهٔ ویژه نیاز ندارند. آزمونِ بیشترین نقطهٔ کد همین وابستگیِ پنهان را کنار می‌زند.
پرسش چهارم: نبودنِ é یعنی متنِ هم‌ظاهر وجود ندارد؟ پاسخ: فقط نبودنِ همان توالیِ نقاطِ کد را نشان می‌دهد. تصمیم دربارهٔ نرمال‌سازی، نیم‌فاصله و مرزِ واژه باید پیش از نمایه و پرسش، یکسان و مستند اتخاذ شود؛ در آن صورت جایگاه‌ها به متنِ تبدیل‌شده تعلق دارند. منابع در ۲۶ مهر ۱۴۰۵ خوانده شده‌اند؛ این آموزش، خبرِ تازه یا تضمینِ کیفیتِ جست‌وجوی فارسی نیست.
منابع و مطالعهٔ بیشتر
- پرینستون؛ فصل6.3 آرایه‌های پسوند
- پایتون3.14؛ مقایسهٔ مقدار و ترتیبِ نقاطِ کد
- پایتون3.14؛ قراردادِ مرزهای bisect
بررسی منابع: ۲۶ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.
