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

چهار الگو را به ترتیب ('R17','17','7R','R') میدهیم. هویتِ هرکدام، شمارهٔ صفرمبنای آن در همین ورودی است. متنِ دستی XR17R17 هفت نقطهٔ کد دارد. در پایانِ نخستین R17، دو الگو با هویتهای صفر و یک تمام شدهاند؛ رشتهٔ 17 پسوندِ R17 است، اما همان شناسهٔ الگو نیست.
درسِ دانشگاه مریلند دربارهٔ Aho–Corasick، مسئلهٔ یافتنِ همهٔ الگوها را با درختِ مشترک و پیوندهای شکست توضیح میدهد. اینجا درخت فقط آغازهای مشترکِ الگوها را نگه میدارد؛ متن در آن ذخیره نمیشود. درخت را یک بار میسازیم و برای هر متنِ منطقی، پیمایشگرِ مستقل میگیریم.
در جستوجوی قطعهای با KMP، تنها یک الگوی ثابت داشتیم. تفاوتِ حاضر، صرفاً اجرای همان تابع با یک فهرست نیست: حالتِ مشترک، پسوندهای آغازِ همهٔ الگوها را دنبال میکند و میتواند در یک نقطه چند هویت تحویل بدهد. همین خروجیِ چندگانه، قرارداد و آزمونِ تازه میخواهد.
سازنده tuple واقعی از str واقعیِ ناتهی میپذیرد؛ رشتهٔ تکراری خطاست. نمیخواهیم دو هویتِ مبهم را بیاعلان یکی کنیم. مجموعهٔ تهی مجاز است و هیچ رخدادی ندارد. الگوی تهی را رد میکنیم، چون گزارشِ آن در تمام مرزهای متن، مسئلهٔ متفاوتی است. سقفِ کوچکِ ساختگی برای تعداد یا طولِ الگو تعیین نشده؛ حافظهٔ موجود همچنان محدود است.
۲. مسیرِ شکست و پیوندِ خروجی دو کار متفاوت دارند

گرهٔ درخت، رشتهٔ روی مسیرِ ریشه تا خودش را نشان میدهد. علامتِ پایانِ الگو مستقل از داشتنِ فرزند است؛ R هم الگوی کامل است و هم آغازِ R17. مانند درسِ تکمیل پیشوند با Trie، پایان را با برگ یکی نمیگیریم؛ اما اینجا پیشنهادِ واژه یا مرتبسازی بر اساس فراوانی نداریم.
پیوندِ شکستِ یک گره به بلندترین پسوندِ سرهٔ مسیرش میرود که هنوز پیشوندِ یکی از الگوهاست. سره یعنی کوتاهتر از کلِ مسیر. وقتی نویسهٔ بعدی یالِ مستقیم ندارد، روی این پیوند عقب میرویم تا ادامهٔ سازگار یا ریشه پیدا شود. همان نویسهٔ تازه سپس بررسی میشود؛ عقب رفتنِ حالت، به معنی عقب بردنِ جایگاهِ متن نیست.
پیوندِ خروجی به نزدیکترین گرهٔ پایانالگو در زنجیرهٔ شکست اشاره میکند؛ ممکن است اصلاً چنین گرهای نباشد. پس از مصرفِ یک نویسه، پایانِ خودِ گره و سپس تمام این پیوندها گزارش میشوند. برای R17، گرهٔ 17 نیز پایان است. نادیده گرفتنِ این مسیر، رخدادِ کوتاهتر را حذف میکند، حتی وقتی ادامهٔ خواندنِ متن درست باشد.
ساخت با پیمایشِ عرضی انجام میشود تا پیوندهای لازمِ عمقهای کمتر آماده باشند. همهٔ فهرستهای خروجی را در هر گره کپی نمیکنیم؛ فقط اشارهگرِ خروجی نگه میداریم و هنگام گزارش دنبال میکنیم. درسِ مریلند همین تمایزِ شکست و خروجی را شرح میدهد. شکلها و رشتههای مثالِ آن منبع در داده یا تصویرِ این مقاله بازتولید نشدهاند.
۳. جایگاه و ترتیبِ رخدادها را قرارداد کنیم

هر Hit سه عدد دارد: هویتِ الگو، آغاز و پایانِ نیمهباز. پایان، شمارِ نقاطِ کدِ مصرفشده است و آغاز با کم کردنِ طولِ همان الگو به دست میآید. رخدادها ابتدا به ترتیبِ پایان و در پایانِ برابر، به ترتیبِ صعودیِ هویتِ ورودیاند. ترتیبِ شاخهها یا طولِ الگو، قاعدهٔ تساویِ ما نیست.
این سیاست «همهٔ رخدادها» است، نه انتخابِ اولین یا بلندترین رخدادِ بدون همپوشانی. مستندات رسمیِ MatchKind در بستهٔ aho-corasick نسخهٔ 1.1.5 نشان میدهد این معناها متفاوتاند. از آن منبع فقط تمایزِ معنا را میگیریم؛ اجرای Rust، همسانیِ کاملِ API، ترتیبِ خروجی یا offset بایتیِ آن را ادعا نمیکنیم.
خوراکِ دستی قطعههای ('XR','1','','7R','17') است. پنج فراخوانی به ترتیب یک، صفر، صفر، چهار و دو رخداد میدهند. در پایانِ چهار، بازههای [1,4) و [2,4) داریم؛ در پایانِ پنج، 7R و R با آغازهای سه و چهار گزارش میشوند. در پایانِ هفت نیز دو رخدادِ دیگر تمام میشوند.
پیمایشگر حالت و جایگاه را میان قطعهها نگه میدارد. قطعهٔ تهی پایانِ سند نیست؛ چیزی را بازپخش یا پاک نمیکند. برای سندِ جدا پیمایشگرِ تازه لازم است تا انتهای یک سند با آغازِ بعدی تطبیق نشود. نوعِ نامعتبر پیش از کار رد میشود؛ این کنترل به معنی تضمینِ تراکنش در برابر کمبود حافظه یا دستکاریِ داخلی نیست.
۴. خروجیِ چندگانه را با برشِ مستقل بسنجیم

کدِ کامل با Python 3.14.5 و فقط کتابخانهٔ استاندارد اجرا شده است. مسیر اصلی، قطعههای گذشته را دوباره به هم نمیچسباند. مرجعِ مستقل، متنِ کاملِ آزمون را دارد و برای هر پایان، برشهای هماندازهٔ همهٔ الگوها را مستقیم مقایسه میکند؛ هیچ درخت، پیوند یا حالتِ ماشین را برای ساختِ پاسخ فراخوانی نمیکند.
"""Original Unicode-codepoint multi-pattern scanner with terminal output links."""
from collections import deque
from dataclasses import dataclass, field, asdict, FrozenInstanceError
from itertools import product
import json
import platform
@dataclass
class _Node:
edges: dict = field(default_factory=dict)
fail: int = 0
output: int = -1
terminal: int | None = None
@dataclass(frozen=True)
class Hit:
pattern_id: int
start: int
end: int
class Aho:
def __init__(self, patterns):
if type(patterns) is not tuple or any(type(p) is not str or not p for p in patterns):
raise ValueError('exact tuple of nonempty actual str patterns required')
if len(set(patterns)) != len(patterns):
raise ValueError('duplicate patterns have no distinct identity in this contract')
self.patterns = patterns
nodes = [_Node()]
for identity, pattern in enumerate(patterns):
v = 0
for char in pattern:
if char not in nodes[v].edges:
nodes[v].edges[char] = len(nodes)
nodes.append(_Node())
v = nodes[v].edges[char]
nodes[v].terminal = identity
queue = deque(nodes[0].edges.values())
while queue:
v = queue.popleft()
for char, child in nodes[v].edges.items():
candidate = nodes[v].fail
while candidate and char not in nodes[candidate].edges:
candidate = nodes[candidate].fail
failure = nodes[candidate].edges.get(char, 0)
nodes[child].fail = failure
nodes[child].output = (failure if nodes[failure].terminal is not None
else nodes[failure].output)
queue.append(child)
self._nodes = tuple(nodes)
def scanner(self):
return Scanner(self)
class Scanner:
def __init__(self, machine):
self._machine, self._state, self._position = machine, 0, 0
@property
def position(self):
return self._position
def feed(self, chunk):
if type(chunk) is not str:
raise ValueError('actual str chunk required; decode bytes separately')
nodes, patterns = self._machine._nodes, self._machine.patterns
state, position, results = self._state, self._position, []
for char in chunk:
while state and char not in nodes[state].edges:
state = nodes[state].fail
state = nodes[state].edges.get(char, 0)
position += 1
identities = []
target = state
while target != -1:
identity = nodes[target].terminal
if identity is not None:
identities.append(identity)
target = nodes[target].output
# Own endpoint tie policy, not a claim of identical library ordering.
for identity in sorted(identities):
results.append(Hit(identity, position - len(patterns[identity]), position))
self._state, self._position = state, position
return tuple(results)
def brute_force(patterns, text):
"""Independent endpoint/slice equality oracle, no automaton/failure links."""
return tuple(Hit(i, end - len(p), end)
for end in range(1, len(text) + 1)
for i, p in enumerate(patterns)
if end >= len(p) and text[end - len(p):end] == p)
def node_labels(machine):
"""Test-only reconstruction of trie labels, not used during text scanning."""
labels = {0: ''}
todo = [0]
for v in todo:
for char, child in machine._nodes[v].edges.items():
labels[child] = labels[v] + char
todo.append(child)
return labels
def rejects(call):
try:
call()
except ValueError:
return True
return False
def main():
patterns = ('R17', '17', '7R', 'R')
machine = Aho(patterns)
chunks = ('XR', '1', '', '7R', '17')
scanner = machine.scanner()
batches = tuple(scanner.feed(c) for c in chunks)
hits = sum(batches, ())
literal = (Hit(3, 1, 2), Hit(0, 1, 4), Hit(1, 2, 4),
Hit(2, 3, 5), Hit(3, 4, 5), Hit(0, 4, 7), Hit(1, 5, 7))
checks = {}
checks['literal_seven_id_start_end_events_across_chunks'] = hits == literal
checks['literal_two_suffix_outputs_same_end_and_id_order'] = (
batches[3] == literal[1:5] and batches[2] == () and scanner.position == 7)
labels = node_labels(machine); inverse = {s: v for v, s in labels.items()}
checks['literal_failure_and_terminal_output_are_distinct_roles'] = (
labels[machine._nodes[inverse['R17']].fail] == '17'
and labels[machine._nodes[inverse['R17']].output] == '17'
and labels[machine._nodes[inverse['7R']].output] == 'R')
words = ('a', 'b', 'aa', 'ab', 'ba', 'bb')
texts = tuple(''.join(t) for n in range(5) for t in product('ab', repeat=n))
cases = 0
for enabled in product((False, True), repeat=len(words)):
pats = tuple(p for p, on in zip(words, enabled, strict=True) if on)
compiled = Aho(pats)
for text in texts:
expected = brute_force(pats, text)
for cut in range(len(text) + 1):
stream = compiled.scanner()
got = stream.feed(text[:cut]) + stream.feed('') + stream.feed(text[cut:])
assert got == expected and stream.position == len(text)
cases += 1
checks['all_dictionary_text_cut_slice_oracles_8256_cases_ONE_group'] = cases == 8256
dense = ('aaaa', 'aaa', 'aa', 'a')
many = Aho(dense).scanner().feed('aaaaa')
checks['dense_overlaps_follow_entire_terminal_output_chain'] = (
many == brute_force(dense, 'aaaaa') and len(many) == 14
and many[-4:] == tuple(Hit(i, i + 1, 5) for i in range(4)))
fallback = ('abab', 'bab', 'aba', 'b')
checks['mismatch_fallback_retains_later_shared_prefix'] = (
Aho(fallback).scanner().feed('abaxabab') == brute_force(fallback, 'abaxabab'))
empty = Aho(()).scanner()
checks['empty_dictionary_has_no_events_but_consumes_text'] = empty.feed('abc') == () and empty.position == 3
uni = ('\u26a1R', 'R', 'é', 'e\u0301', '\x00')
ut = '\U0001f642\u26a1Re\u0301é\x00'
us = Aho(uni).scanner()
uh = us.feed(ut[:4]) + us.feed(ut[4:])
checks['unicode_codepoint_offsets_combining_form_and_NUL'] = (
uh == (Hit(0, 1, 3), Hit(1, 2, 3), Hit(3, 3, 5), Hit(2, 5, 6), Hit(4, 6, 7))
and us.position == len(ut) == 7 and len(ut.encode('utf-8')) == 14)
rev = tuple(reversed(patterns))
def identities_as_strings(pats, events):
return sorted((h.end, pats[h.pattern_id], h.start) for h in events)
checks['reordered_pattern_ids_preserve_occurrence_strings_not_numeric_ids'] = (
identities_as_strings(patterns, hits) == identities_as_strings(rev, Aho(rev).scanner().feed('XR17R17')))
left, right = machine.scanner(), machine.scanner()
first = left.feed('XR1'); rh = right.feed('R17'); lh = left.feed('7')
checks['two_streams_share_compiled_machine_without_sharing_scan_state'] = (
first == (Hit(3, 1, 2),) and lh == (Hit(0, 1, 4), Hit(1, 2, 4))
and rh == (Hit(3, 0, 1), Hit(0, 0, 3), Hit(1, 1, 3))
and (left.position, right.position) == (4, 3))
checks['empty_chunk_neither_replays_nor_resets_state'] = left.feed('') == () and left.position == 4
class TextSubclass(str):
pass
checks['pattern_contract_empty_members_duplicates_and_types_reject'] = all(
rejects(lambda value=value: Aho(value))
for value in (['a'], 'a', ('',), ('a', 'a'), (b'a',), (None,), (TextSubclass('a'),)))
pending = machine.scanner(); before = pending.feed('R1')
errors = all(rejects(lambda x=x: pending.feed(x)) for x in (None, b'7', 7, TextSubclass('7')))
checks['invalid_chunk_types_do_not_advance_partial_match'] = (
before == (Hit(3, 0, 1),) and errors and pending.position == 2
and pending.feed('7') == (Hit(0, 0, 3), Hit(1, 1, 3)))
invariant_nodes = 0
for pats in (patterns, dense, fallback, uni):
compiled = Aho(pats); ls = node_labels(compiled)
for v, label in ls.items():
if v == 0:
continue
suffixes = [(len(s), u) for u, s in ls.items() if len(s) < len(label) and label.endswith(s)]
expected_fail = max(suffixes)[1]
assert compiled._nodes[v].fail == expected_fail
terminals = [(len(p), ls_inv) for ls_inv, p in ls.items()
if len(p) < len(label) and label.endswith(p) and p in pats]
expected_output = max(terminals)[1] if terminals else -1
assert compiled._nodes[v].output == expected_output
invariant_nodes += 1
checks['failure_longest_suffix_and_output_nearest_terminal_invariants'] = invariant_nodes > 0
frozen = hits[0]
try:
frozen.start = 99
immutable = False
except FrozenInstanceError:
immutable = True
checks['returned_hits_are_frozen_integer_records'] = immutable and hits == literal
assert all(type(v) is bool and v for v in checks.values()), checks
print(json.dumps({'python': platform.python_version(), 'dependencies': 'stdlib only',
'patterns_by_id': patterns, 'hand_text': 'XR17R17', 'hand_chunks': chunks,
'hand_events': [asdict(h) for h in hits], 'hand_batch_event_counts': [len(x) for x in batches],
'brute_force_cases_inside_ONE_group': cases, 'dense_overlap_event_count': len(many),
'structural_nodes_inside_ONE_group': invariant_nodes,
'unicode_text_codepoints': len(ut), 'unicode_text_utf8_bytes': len(ut.encode('utf-8')),
'checks': checks, 'unique_check_groups': len(checks), 'all_passed': True,
'limits': 'Exact supplied str substrings and own endpoint/input-ID ordering. No normalization, byte decoding, grapheme/word boundaries, semantic relevance, library API parity, workload benchmark or universal capacity guarantee.'},
ensure_ascii=False, indent=2))
if __name__ == '__main__':
main()
از شش الگوی کوتاهِ دودویی، ۶۴ زیرمجموعه میسازیم. برای ۳۱ متنِ طولِ صفر تا چهار، تمام مرزهای دو قطعه و یک قطعهٔ خالیِ میانی بررسی میشوند. حاصل ۸۲۵۶ مقایسه در یک گروه است. این دامنه، اندازهٔ مجازِ رابط را محدود نمیکند و تعدادِ حالتها نیز به تعدادِ گروهها اضافه نشده است.
در آزمونی جدا، برچسبِ مسیرِ گرهها بازسازی و همهٔ پسوندهای ممکن مستقیماً برشمرده میشوند. بلندترین پیشوندِ پسوندشونده، مرجعِ شکست است و نزدیکترین پایانِ سره، مرجعِ خروجی. ۲۵ گره در چهار واژهنامه داخل همین یک گروهاند. شاهدِ چهار الگوی تودرتو نیز چهار خروجیِ همپایان و چهارده رخدادِ همپوشان را کنترل میکند.
{
"python": "3.14.5",
"dependencies": "stdlib only",
"patterns_by_id": [
"R17",
"17",
"7R",
"R"
],
"hand_text": "XR17R17",
"hand_chunks": [
"XR",
"1",
"",
"7R",
"17"
],
"hand_events": [
{
"pattern_id": 3,
"start": 1,
"end": 2
},
{
"pattern_id": 0,
"start": 1,
"end": 4
},
{
"pattern_id": 1,
"start": 2,
"end": 4
},
{
"pattern_id": 2,
"start": 3,
"end": 5
},
{
"pattern_id": 3,
"start": 4,
"end": 5
},
{
"pattern_id": 0,
"start": 4,
"end": 7
},
{
"pattern_id": 1,
"start": 5,
"end": 7
}
],
"hand_batch_event_counts": [
1,
0,
0,
4,
2
],
"brute_force_cases_inside_ONE_group": 8256,
"dense_overlap_event_count": 14,
"structural_nodes_inside_ONE_group": 25,
"unicode_text_codepoints": 7,
"unicode_text_utf8_bytes": 14,
"checks": {
"literal_seven_id_start_end_events_across_chunks": true,
"literal_two_suffix_outputs_same_end_and_id_order": true,
"literal_failure_and_terminal_output_are_distinct_roles": true,
"all_dictionary_text_cut_slice_oracles_8256_cases_ONE_group": true,
"dense_overlaps_follow_entire_terminal_output_chain": true,
"mismatch_fallback_retains_later_shared_prefix": true,
"empty_dictionary_has_no_events_but_consumes_text": true,
"unicode_codepoint_offsets_combining_form_and_NUL": true,
"reordered_pattern_ids_preserve_occurrence_strings_not_numeric_ids": true,
"two_streams_share_compiled_machine_without_sharing_scan_state": true,
"empty_chunk_neither_replays_nor_resets_state": true,
"pattern_contract_empty_members_duplicates_and_types_reject": true,
"invalid_chunk_types_do_not_advance_partial_match": true,
"failure_longest_suffix_and_output_nearest_terminal_invariants": true,
"returned_hits_are_frozen_integer_records": true
},
"unique_check_groups": 15,
"all_passed": true,
"limits": "Exact supplied str substrings and own endpoint/input-ID ordering. No normalization, byte decoding, grapheme/word boundaries, semantic relevance, library API parity, workload benchmark or universal capacity guarantee."
}
پانزده گروهِ نامدار موفق شدند؛ شاهدِ دستی، بازگشت پس از ناسازگاری، دو پیمایشگرِ مستقل، تغییرِ هویتها با ترتیبِ ورودی، یونیکد و خطاهای نوع نیز سنجیدهاند. این آزمونهای محدود، اثباتِ همهٔ رشتهها نیستند. خروجیِ Hit دارای فیلدهای frozen است، اما گرههای داخلیِ ماشین اشیای معمول پایتوناند؛ تغییرِ دستیِ آنها پشتیبانی نمیشود.
۵. تطبیقِ دقیق را تشخیصِ نام و معنا ننامیم

تعریف رسمیِ str در پایتون، واحدِ رشته را نقطهٔ کدِ یونیکد میداند. در شاهدِ هفتنقطهایِ دارای شکلک، علامتِ ترکیبی و صفر، طولِ UTF-8 چهارده بایت است. برنامه نرمالسازی، خوشهبندیِ نوشتاری، رمزگشایی یا مرزِ واژه ندارد. نوع str بهتنهایی گواهیِ مناسببودنِ متن برای نمایش یا پروتکلِ خارجی نیست.
پرسش اول: چرا 17 همراه R17 گزارش میشود؟ پاسخ: هر دو الگوی اعلامشدهاند و هر دو در همان پایان واقعاً تطبیق دارند. حذفِ کوتاهتر، پاسخِ قرارداد را ناقص میکند. اگر کاربرد فقط نامِ کاملِ قطعه میخواهد، باید سیاستِ قالب و مرز را جدا تعیین کند؛ وقوعِ زیررشته معنای قطعه را ثابت نمیکند.
پرسش دوم: آیا ترتیبِ ورودی اولویتِ حذفِ رخداد است؟ پاسخ: خیر؛ فقط هویت و ترتیبِ گزارش در پایانِ برابر را تعیین میکند. با برعکس کردنِ فهرست، مجموعهٔ رشتهها و بازههای رخداد ثابت میماند، اما شمارههای هویت عوض میشوند. «اولویتِ الگو» و «ترتیبِ تحویلِ همهٔ نتایج» دو قرارداد متفاوتاند.
پرسش سوم: میتوان bytes را مستقیماً خوراک داد؟ پاسخ: خیر؛ این رابط آن را رد میکند. رمزگشای جدا باید شکستنِ یک نویسه میان قطعههای بایتی را مدیریت کند. پس از رمزگشایی نیز جایگاههای این ماشین مربوط به متنِ حاصلاند؛ با جابهجا کردنِ یک offset، نگاشتِ معتبر به بایتهای منبع خودکار ساخته نمیشود.
پرسش چهارم: یک بار خواندنِ متن یعنی حافظه و زمانِ ثابت؟ پاسخ: خیر؛ ماشین الگوها و گرهها را نگه میدارد، خروجیِ هر قطعه ممکن است بزرگ شود و ترتیبِ هویتها در هر پایان مرتب میشود. از پیچیدگیِ نسخههای مرجع، تضمینِ سرعتِ همین پیادهسازی را نتیجه نمیگیریم. منابع در ۲۶ مهر ۱۴۰۵ خوانده شدهاند؛ آموزش خبر تازه، ارزیابیِ جستوجو یا سنجشِ محصول نیست.
منابع و مطالعهٔ بیشتر
- دانشگاه مریلند؛ درس کامل Aho–Corasick و پیوند خروجی
- مستندات رسمی aho-corasick 1.1.5؛ تفاوت معناهای تطبیق
- Python 3.14؛ تعریف رشته و واحد نقطهٔ کد
بررسی منابع: ۲۶ مهر ۱۴۰۵. تحلیلها و پیشنهادهای اجرایی، جمعبندی نویسندهاند.

