فهرست مقاله
در صفحهٔ جست‌وجوی یک واژه‌نامهٔ مهندسی، ممکن است بخواهیم پس از دریافت «توا»، چند واژهٔ آغازشونده با همین رشته را پیشنهاد کنیم. این کار هنوز بازیابیِ سند یا اصلاحِ املای پرسش نیست. در این درس یک Trie کوچک می‌سازیم، فراوانی‌های ورودی را صریح می‌گیریم و قاعدهٔ تساوی را پیش از انتخاب پاسخ تعیین می‌کنیم. داده‌ها و فراوانی‌ها ساختگی‌اند؛ خروجیِ اجراشده فقط درستیِ قراردادِ همین واژه‌نامهٔ محدود را بررسی می‌کند.
۱. پیشوندِ خام را از اصلاحِ پرس‌وجو جدا کنیم
ده مدخل داریم، از جمله توان، توان‌سنج، توان‌سنجی، توالی، ترانس، حسگر و رله. هر مدخل یک رشته و یک عدد صحیحِ مثبتِ ازپیش‌داده‌شده دارد. عدد، فراوانیِ قراردادیِ تمرین است؛ نه آمار کاربران، شمار سندهای اینترنت یا احتمالِ نیت کاربر. پیشنهاد فقط از مدخل‌های موجود انتخاب می‌شود و برنامه واژهٔ تازه‌ای تولید نمی‌کند.
بحثِ پیشوند در واژه‌نامهٔ بازیابی اطلاعات، پیمودن نمادهای آغازین و سپس برشمردن واژه‌های همان بخش از درخت را توضیح می‌دهد؛ بازیابی سند را مرحلهٔ بعدی می‌داند. اینجا همان مسئلهٔ محدودِ یافتن واژه‌های آغازشونده را با درختِ صریحِ خودمان پیاده می‌کنیم. قالبِ جست‌وجوی دارای ستاره، پسوند، واژهٔ میانی و درخت B متوازن در برنامه وجود ندارد.
رشتهٔ پرسش بدون دست‌کاری مقایسه می‌شود. درس نرمال‌سازی و برخورد کلیدهای فارسی سیاستِ ساخت کلید را جدا بررسی می‌کند. در این نمونه، دو یاء عربی و فارسی، نیم‌فاصله و شکل‌های ترکیبی خودکار یکی نمی‌شوند. انتخابِ چنین سیاستی باید در سازندهٔ واژه‌نامه و دریافتِ پرسش هماهنگ باشد؛ نامِ Trie به‌تنهایی آن تصمیم را نمی‌گیرد.
۲. درختِ نقاط کد و پایانِ مستقلِ واژه را بسازیم
طبق تعریف رشته در پایتون، واحدِ پیمایشِ str نقطهٔ کد یونیکد است. از ریشه شروع می‌کنیم و برای هر نقطهٔ کد، یک یالِ نام‌گذاری‌شده به گرهٔ بعدی داریم. آغازهای مشترک، مسیر مشترک پیدا می‌کنند؛ پس توان و توان‌سنج تا پایانِ رشتهٔ توان از همان مسیر می‌گذرند. این واحد را بایت UTF-8 یا یک فشار کلیدِ کاربر نمی‌نامیم.
هر گره دو نقشِ مستقل دارد: فرزندان و علامتِ پایانِ واژه. گرهٔ پایانِ توان باید فراوانیِ چهار را نگه دارد و هم‌زمان شاخه‌ای برای ادامهٔ توان‌سنج داشته باشد. گرهٔ پایانِ توان‌سنج نیز می‌تواند به توان‌سنجی ادامه پیدا کند. اگر کامل‌بودن واژه را با بی‌فرزندبودن یکی بگیریم، بعضی مدخل‌های درست از پیشنهادها حذف می‌شوند.
سازنده حداکثر سی‌ودو زوجِ یکتا می‌پذیرد. ظرف بیرونی و هر زوج باید tuple واقعی باشند؛ واژه str دقیقِ ناتهی با حداکثر بیست‌وچهار نقطهٔ کد است. فراوانی int دقیق از یک تا یک میلیون است و bool پذیرفته نمی‌شود. مدخلِ تکراری را جمع یا جایگزین نمی‌کنیم؛ خطا می‌دهیم تا منشأِ اختلاف فراوانی پنهان نشود. تمام مدخل‌ها پیش از ساختِ گره‌ها اعتبارسنجی می‌شوند.
فاصلهٔ سفید، نقاطِ صفر تا سی‌ویک، ۱۲۷ تا ۱۵۹ و بازهٔ جانشینِ یونیکد در متن رد می‌شوند. این فهرستِ محدود، قراردادِ ورودی است و پالایش امنیتیِ همهٔ متن‌ها نیست. نیم‌فاصله حفظ می‌شود. پیشوند می‌تواند تهی باشد و همان سقف طول را دارد؛ رشتهٔ تهی در این رابط یعنی انتخاب از کل واژه‌نامه، نه خطای ورودی.
۳. فراوانی و تساوی را پیش از برشِ پاسخ تعریف کنیم
پس از رسیدن به گرهٔ پیشوند، همهٔ پایان‌های واژه در زیر‌درخت را جمع می‌کنیم؛ پایانِ خودِ گره هم فراموش نمی‌شود. سپس بر اساس فراوانیِ نزولی و در تساوی بر اساس رشتهٔ خامِ صعودی مرتب می‌کنیم. مرجع مقایسهٔ پایتون، ترتیبِ رشته را بر مبنای مقدار عددی نقاط کد تعریف می‌کند. این ترتیب، مرتب‌سازی زبانیِ فارسی یا ترجیحِ معنایی نیست.
برای پیشوند توا، سه مدخلِ توالی، توان‌سنج و توان‌سنجی فراوانیِ نه دارند و توان فراوانیِ چهار دارد. توالی پیش از دو تای دیگر می‌آید، زیرا پس از توا، لام پیش از نون است. میان دو رشتهٔ توان‌سنج و توان‌سنجی، رشتهٔ کوتاه‌ترِ مشترک مقدم است. با حدِ دو، نتیجه توالی و توان‌سنج خواهد بود. این جواب از قاعدهٔ اعلام‌شده می‌آید، نه از اینکه کدام واژه برای کاربر مفیدتر است.
بُرش را بعد از گردآوری و مرتب‌سازی انجام می‌دهیم. توقف در نخستین پایانِ واژه یا نخستین دو گرهٔ پیمایش می‌تواند توانِ کم‌فراوانی را زودتر انتخاب کند. ترتیبِ درجِ مدخل‌ها و ترتیبِ فرزندان، قاعدهٔ رتبه‌بندی ما نیستند. حدِ خروجی، عدد صحیحِ دقیقِ صفر تا سی‌ودو است؛ صفر خروجی تهی می‌دهد، اما اعتبارسنجیِ پیشوند را دور نمی‌زند.
۴. مسیرِ درخت را با مرجعِ مرتب و bisect بسنجیم
کد زیر با Python 3.14.5 و فقط کتابخانهٔ استاندارد اجرا شده است. تابعِ complete نتیجه‌ای از زوج‌های واژه و فراوانی می‌دهد و نمونه‌های ورودی را بازنویسی نمی‌کند. ساختار داخلی با اشیای معمول پایتون ساخته شده است؛ خصوصی‌نامیدنِ ریشه به معنی تغییرناپذیریِ سخت یا مرز امنیتی نیست. در رابط آموزشی، افزودن یا حذفِ تدریجیِ واژه نداریم؛ واژه‌نامهٔ تازه، درختِ تازه می‌سازد.
"""Own bounded raw-codepoint trie; finite frequency ranking, not spell correction."""
from bisect import bisect_left
import itertools
import json
import platform
MAX_TERMS = 32
MAX_POINTS = 24
MAX_FREQUENCY = 1_000_000
def _text(value, allow_empty):
if type(value) is not str:
raise TypeError("actual str required")
if len(value) > MAX_POINTS or (not value and not allow_empty):
raise ValueError("text length outside contract")
for point in value:
number = ord(point)
if (point.isspace() or number < 32 or 127 <= number <= 159
or 0xD800 <= number <= 0xDFFF):
raise ValueError("whitespace, selected controls or surrogates forbidden")
class _Node:
def __init__(self):
self.children = {}
self.terminal = None
class PrefixTrie:
def __init__(self, entries):
if type(entries) is not tuple:
raise TypeError("entries must be an actual tuple")
if len(entries) > MAX_TERMS:
raise ValueError("too many terms")
seen = set()
for entry in entries:
if type(entry) is not tuple or len(entry) != 2:
raise TypeError("each entry must be an actual (term, frequency) tuple")
word, frequency = entry
_text(word, allow_empty=False)
if word in seen:
raise ValueError("duplicate raw term")
seen.add(word)
if type(frequency) is not int:
raise TypeError("frequency must be an actual int")
if not 1 <= frequency <= MAX_FREQUENCY:
raise ValueError("frequency outside contract")
self._root = _Node()
for word, frequency in entries:
node = self._root
for point in word:
if point not in node.children:
node.children[point] = _Node()
node = node.children[point]
node.terminal = (word, frequency)
def complete(self, prefix, k=5):
_text(prefix, allow_empty=True)
if type(k) is not int:
raise TypeError("k must be an actual int")
if not 0 <= k <= MAX_TERMS:
raise ValueError("k outside contract")
if k == 0:
return ()
node = self._root
for point in prefix:
node = node.children.get(point)
if node is None:
return ()
matches = []
stack = [node]
while stack:
current = stack.pop()
if current.terminal is not None:
matches.append(current.terminal)
stack.extend(current.children.values())
# Enumerate every matching terminal before applying the output limit.
matches.sort(key=lambda item: (-item[1], item[0]))
return tuple(matches[:k])
def sorted_bisect_reference(entries, prefix, k):
"""Valid-input oracle: no trie construction, nodes or traversal."""
weights = dict(entries)
words = sorted(weights)
cursor = bisect_left(words, prefix)
matches = []
while cursor < len(words) and words[cursor].startswith(prefix):
word = words[cursor]
matches.append((word, weights[word]))
cursor += 1
# Stable two-pass ordering: lexical order first, then frequency descending.
matches.sort(key=lambda item: item[0])
matches.sort(key=lambda item: item[1], reverse=True)
return tuple(matches[:k])
def rejects(function, *arguments):
try:
function(*arguments)
except (TypeError, ValueError):
return True
return False
def run_example():
entries = (("توان", 4), ("توان‌سنج", 9), ("توان‌سنجی", 9), ("توالی", 9),
("ترانس", 6), ("حسگر", 8), ("حسگرک", 3), ("رله", 5),
("يک", 1), ("یک", 2))
trie = PrefixTrie(entries)
checks = {}
hand = (("توالی", 9), ("توان‌سنج", 9))
checks["literal_hand_frequency_and_raw_lexical_tie_top_two"] = (
trie.complete("توا", 2) == hand)
checks["terminal_word_with_children_not_lost_or_early_cut"] = (
trie.complete("توان", 32)
== (("توان‌سنج", 9), ("توان‌سنجی", 9), ("توان", 4)))
universe = ("ا", "اب", "ب", "با")
prefixes = ("", "ا", "اب", "ب", "با", "ج")
oracle_ok = True
oracle_cases = lexicons = 0
# 0 omits a word, 1/2 assign its supplied synthetic frequency.
for states in itertools.product((0, 1, 2), repeat=len(universe)):
lexicon = tuple((word, frequency) for word, frequency in zip(universe, states)
if frequency)
small = PrefixTrie(lexicon)
lexicons += 1
for prefix in prefixes:
for k in range(5):
oracle_ok = oracle_ok and small.complete(prefix, k) == (
sorted_bisect_reference(lexicon, prefix, k))
oracle_cases += 1
checks["independent_sorted_bisect_2430_cases_one_group"] = (
oracle_ok and lexicons == 81 and oracle_cases == 2430)
reversed_trie = PrefixTrie(tuple(reversed(entries)))
checks["entry_order_does_not_choose_tie_winner"] = all(
trie.complete(prefix, k) == reversed_trie.complete(prefix, k)
for prefix in ("", "توا", "توان", "حس", "ی") for k in (0, 1, 3, 32))
checks["empty_dictionary_empty_prefix_and_absent_path"] = (
PrefixTrie(()).complete("", 5) == ()
and trie.complete("", 1) == (("توالی", 9),)
and trie.complete("ناموجود", 5) == () and trie.complete("", 0) == ())
checks["raw_arabic_and_persian_yeh_kept_distinct"] = (
trie.complete("ي", 5) == (("يک", 1),)
and trie.complete("ی", 5) == (("یک", 2),))
checks["zwnj_is_an_explicit_codepoint_not_removed"] = (
trie.complete("توان", 5) == (("توان‌سنج", 9), ("توان‌سنجی", 9))
and trie.complete("توانس", 5) == ())
special_entries = (("e\u0301", 3), ("é", 2), ("😀x", 4),
("\U0010ffffa", 5), ("\U0010ffff", 1))
special = PrefixTrie(special_entries)
checks["codepoints_not_utf8_bytes_or_canonical_equivalence"] = (
special.complete("e", 5) == (("e\u0301", 3),)
and special.complete("é", 5) == (("é", 2),)
and special.complete("😀", 5) == (("😀x", 4),)
and len("😀") == 1 and len("😀".encode("utf8")) == 4)
checks["highest_codepoint_prefix_needs_no_upper_sentinel"] = (
special.complete("\U0010ffff", 5)
== (("\U0010ffffa", 5), ("\U0010ffff", 1))
== sorted_bisect_reference(special_entries, "\U0010ffff", 5))
checks["entry_shape_duplicate_and_term_count_errors"] = all((
rejects(PrefixTrie, list(entries)), rejects(PrefixTrie, (("a",),)),
rejects(PrefixTrie, (["a", 1],)),
rejects(PrefixTrie, (("a", 1), ("a", 2))),
rejects(PrefixTrie, tuple((str(i), 1) for i in range(33)))))
class StringSubclass(str):
pass
text_bad = (b"a", True, StringSubclass("a"), "a" * 25,
"a b", "a\x00", "\x80", "\ud800")
frequency_bad = (True, 1.0, "1", 0, -1, 1_000_001, 10 ** 100)
checks["text_and_frequency_types_lengths_and_ranges"] = (
all(rejects(PrefixTrie, ((word, 1),)) for word in ("",) + text_bad)
and all(rejects(trie.complete, prefix, 0) for prefix in text_bad)
and all(rejects(PrefixTrie, (("a", frequency),)) for frequency in frequency_bad))
checks["k_exact_integer_and_inclusive_range"] = all(
rejects(trie.complete, "توان", k) for k in (True, 1.0, "1", -1, 33))
boundary_entries = tuple((f"{i:02d}" + "x" * 22, MAX_FREQUENCY)
for i in range(MAX_TERMS))
boundary = PrefixTrie(boundary_entries)
checks["maximum_terms_points_frequency_and_k_accepted"] = (
len(boundary.complete("", 32)) == 32
and boundary.complete(boundary_entries[0][0], 32) == (boundary_entries[0],))
before = trie.complete("", 32)
for prefix in ("", "ت", "توان", "توان", "حس", "ناموجود"):
trie.complete(prefix, 3)
checks["queries_preserve_entries_and_future_results"] = (
trie.complete("", 32) == before and entries[0] == ("توان", 4)
and trie.complete("توا", 2) == hand)
assert all(type(value) is bool and value for value in checks.values())
return {
"runtime": {"python": platform.python_version(), "dependencies": "stdlib only"},
"contract": {"maximum_terms": MAX_TERMS, "maximum_word_or_prefix_codepoints": MAX_POINTS,
"maximum_supplied_frequency": MAX_FREQUENCY, "k_range_inclusive": [0, MAX_TERMS],
"ranking": "frequency descending, then exact raw Python string ascending",
"normalization_casefold_fuzzy_matching": False,
"frequency_origin": "synthetic supplied integers, not collected traffic"},
"fixture_entries": entries, "hand_prefix": "توا", "hand_k": 2,
"hand_results": trie.complete("توا", 2),
"terminal_prefix_results": trie.complete("توان", 32),
"global_top_one_for_empty_prefix": trie.complete("", 1),
"zwnj_prefix_results": trie.complete("توان", 5),
"oracle_lexicons_inside_one_group": lexicons,
"oracle_queries_inside_one_group": oracle_cases,
"checks": checks, "check_count": len(checks), "all_passed": True,
"limits": ["Finite raw-codepoint prefix completion only, not documents or semantics",
"No normalization, grapheme segmentation, IME or language-wide guarantee",
"Subtree fully enumerated then sorted; no prefix-length-plus-k complexity claim",
"No latency, RAM, production relevance or security measurement"]}
if __name__ == "__main__":
print(json.dumps(run_example(), ensure_ascii=False, indent=2))
مرجع مستقل، هیچ گره یا پیمایشِ Trie ندارد. واژه‌ها را خام مرتب می‌کند و با bisect_left نخستین جای ممکن برای پیشوند را می‌یابد. از آن نقطه، واژه‌های دارای startswith را تا پایانِ بخشِ پیوسته می‌خواند. سپس با مرتب‌سازیِ پایدارِ دوم بر فراوانی، ترتیبِ خامِ اعضای مساوی را حفظ می‌کند؛ پاسخ با مسیرِ درخت مقایسه می‌شود.
برای تعیین انتهای بخش، حرفِ ساختگیِ «بزرگ‌تر از همهٔ یونیکد» نمی‌سازیم. ادامهٔ خواندن تا نخستین واژهٔ بدون پیشوند کافی است. شاهدِ بیشترین نقطهٔ کد نیز همین مرز را کنترل می‌کند. آن شاهد صرفاً رشته‌ای برای آزمون است و نامِ قطعه یا واژهٔ قابل نمایشِ یک زبان معرفی نمی‌شود. نمونهٔ علامتِ ترکیبی هم فقط نشان می‌دهد برنامه نرمال‌سازی اجرا نکرده است.
{
"runtime": {
"python": "3.14.5",
"dependencies": "stdlib only"
},
"contract": {
"maximum_terms": 32,
"maximum_word_or_prefix_codepoints": 24,
"maximum_supplied_frequency": 1000000,
"k_range_inclusive": [
0,
32
],
"ranking": "frequency descending, then exact raw Python string ascending",
"normalization_casefold_fuzzy_matching": false,
"frequency_origin": "synthetic supplied integers, not collected traffic"
},
"fixture_entries": [
[
"توان",
4
],
[
"توان‌سنج",
9
],
[
"توان‌سنجی",
9
],
[
"توالی",
9
],
[
"ترانس",
6
],
[
"حسگر",
8
],
[
"حسگرک",
3
],
[
"رله",
5
],
[
"يک",
1
],
[
"یک",
2
]
],
"hand_prefix": "توا",
"hand_k": 2,
"hand_results": [
[
"توالی",
9
],
[
"توان‌سنج",
9
]
],
"terminal_prefix_results": [
[
"توان‌سنج",
9
],
[
"توان‌سنجی",
9
],
[
"توان",
4
]
],
"global_top_one_for_empty_prefix": [
[
"توالی",
9
]
],
"zwnj_prefix_results": [
[
"توان‌سنج",
9
],
[
"توان‌سنجی",
9
]
],
"oracle_lexicons_inside_one_group": 81,
"oracle_queries_inside_one_group": 2430,
"checks": {
"literal_hand_frequency_and_raw_lexical_tie_top_two": true,
"terminal_word_with_children_not_lost_or_early_cut": true,
"independent_sorted_bisect_2430_cases_one_group": true,
"entry_order_does_not_choose_tie_winner": true,
"empty_dictionary_empty_prefix_and_absent_path": true,
"raw_arabic_and_persian_yeh_kept_distinct": true,
"zwnj_is_an_explicit_codepoint_not_removed": true,
"codepoints_not_utf8_bytes_or_canonical_equivalence": true,
"highest_codepoint_prefix_needs_no_upper_sentinel": true,
"entry_shape_duplicate_and_term_count_errors": true,
"text_and_frequency_types_lengths_and_ranges": true,
"k_exact_integer_and_inclusive_range": true,
"maximum_terms_points_frequency_and_k_accepted": true,
"queries_preserve_entries_and_future_results": true
},
"check_count": 14,
"all_passed": true,
"limits": [
"Finite raw-codepoint prefix completion only, not documents or semantics",
"No normalization, grapheme segmentation, IME or language-wide guarantee",
"Subtree fully enumerated then sorted; no prefix-length-plus-k complexity claim",
"No latency, RAM, production relevance or security measurement"
]
}چهارده گروهِ نام‌دار موفق‌اند. برای چهار واژهٔ کوتاه، هرکدام سه حالتِ نبودن، فراوانیِ یک یا دو دارد؛ هشتاد‌ویک واژه‌نامه ساخته می‌شود. شش پیشوند و پنج حدِ خروجی، ۲۴۳۰ مقایسه را داخل یک گروه مرجع مستقل تشکیل می‌دهند. شاهدِ دستی، پایانِ دارای فرزند، ترتیبِ ورودی، نیم‌فاصله، نوع‌ها و مرزها جدا سنجیده شده‌اند. تکرارِ اجرا یا شمارِ حالت‌های یک حلقه، گروهِ تازه محسوب نمی‌شود.
۵. تکمیلِ پیشوند را کیفیتِ جست‌وجو ننامیم
این پیاده‌سازی همهٔ زیر‌درختِ مربوط را می‌پیماید و همهٔ نامزدهایش را مرتب می‌کند. بنابراین حتی با حدِ یک، کارِ تابع فقط خواندنِ پیشوند و تحویلِ یک مدخل نیست. زمان، حافظه، تأخیرِ تایپ یا کاراییِ محصول اندازه‌گیری نشده است. سیاستِ فراوانی نیز از ورودی می‌آید؛ عدد بزرگ‌تر، ارتباط بیشتر با پرسش یا جوازِ نمایشِ یک واژه را ثابت نمی‌کند.
پرسش اول: چرا توان با وجودِ تطابقِ کامل، نخستین پیشنهاد نیست؟ پاسخ: تطابقِ کامل در این قرارداد امتیاز ویژه ندارد؛ فراوانیِ چهار پس از دو ادامهٔ نه‌تایی می‌آید. برای پیشوندِ توان، ترتیب توان‌سنج، توان‌سنجی و سپس توان است.
پرسش دوم: حدِ صفر ورودیِ خراب را مجاز می‌کند؟ پاسخ: خیر؛ نوع و طول و نقاطِ ممنوعِ پیشوند، پیش از بازگرداندنِ پاسخِ تهی بررسی می‌شوند. مقدار صفر فقط اندازهٔ خروجیِ معتبر را تعیین می‌کند.
پرسش سوم: پیشوندِ تهی با حدِ یک چه می‌دهد؟ پاسخ: توالی با فراوانیِ نه؛ همهٔ مدخل‌ها نامزدند و تساویِ بیشترین فراوانی با ترتیبِ خام حل می‌شود. واژه‌نامهٔ تهی در همین پرسش خروجی تهی دارد.
پرسش چهارم: اگر پرسش غلط املایی داشته باشد، نزدیک‌ترین واژه پیدا می‌شود؟ پاسخ: خیر؛ مسیرِ متفاوت ممکن است هیچ پیشنهادی ندهد. پیشنهاد با فاصلهٔ ویرایشی مسئله و قراردادِ دیگری دارد. این برنامه فهمِ فارسی، روش ورود متن، رتبه‌بندی سند و ارزیابیِ پاسخ را پیاده نمی‌کند؛ پیشنهادِ محاسباتی باید با همین مرزها تفسیر شود.
منابع و مطالعهٔ بیشتر
- کتاب بازیابی اطلاعات؛ پیمایشِ پیشوند و جدایی از بازیابی سند
- Python 3.14؛ bisect و جایگاهِ آغاز در فهرست مرتب
- Python 3.14؛ رشتهٔ نقاط کد، startswith و پایداری مرتب‌سازی
- Python 3.14؛ ترتیبِ خامِ رشته‌های یونیکد
بررسی منابع: ۲۶ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.
