ตัวเติมคำอัตโนมัติแบบง่ายๆสำหรับใช้ในเชลล์
ปัญหา
ฉันกำลังเขียนเชลล์ธรรมดาและฉันต้องการมีคุณสมบัติเติมข้อความอัตโนมัติที่ดีที่ bash มีเมื่อคุณพิมพ์คำบางส่วนจากนั้นกดtab:

ตอนนี้สามารถทำงานได้อย่างอิสระจากเชลล์ แต่มีคุณสมบัติที่ช่วยให้ค้นหาคำสั่งในระบบได้ ตัวอย่าง:
>>> table = make_lookup_table_from(["hell", "water", "help", "air", "hello", "fire", "earth"])
>>> find_matching(table, "hel")
['hell', 'hello', 'help']
>>> table = make_lookup_table_from_path()
>>> find_matching(table, "gcc-")
['gcc-ar', 'gcc-ar-8', 'gcc-ar-9', 'gcc-nm', 'gcc-nm-8', 'gcc-nm-9', 'gcc-ranlib', 'gcc-ranlib-8', 'gcc-ranlib-9', 'gcc-8', 'gcc-9']
>>> find_matching(table, "pyth")
['python3.8', 'python3.8-config', 'python3', 'python3-qr', 'python3-futurize', 'python3-pasteurize', 'python3-tor-prompt', 'python3-config', 'python3-wsdump', 'python', 'python-argcomplete-check-easy-install-script', 'python-argcomplete-check-easy-install-script3', 'python-argcomplete-tcsh', 'python-argcomplete-tcsh3', 'python-config', 'python-faraday', 'python2-config', 'python2-futurize', 'python2-pasteurize', 'python2-pbr', 'python2', 'python2.7-config', 'python2.7']
มันทำงานอย่างไร:
คำแต่ละคำจะถูกใส่ลงในพจนานุกรมที่ซ้อนกันทีละตัวอักษรจากนั้นจะสิ้นสุดด้วยอักขระว่างเพื่อทำเครื่องหมายจุดสิ้นสุดของคำ:
>>> make_lookup_table_from(["hell", "water", "help", "air", "hello", "fire", "earth"])
{'h': {'e': {'l': {'l': {'\x00': {}, 'o': {'\x00': {}}}, 'p': {'\x00': {}}}}}, 'w': {'a': {'t': {'e': {'r': {'\x00': {}}}}}}, 'a': {'i': {'r': {'\x00': {}}}}, 'f': {'i': {'r': {'e': {'\x00': {}}}}}, 'e': {'a': {'r': {'t': {'h': {'\x00': {}}}}}}}
ในการค้นหาเพื่อค้นหารายการที่ตรงกันต้นไม้จะถูกเดินไปจนกว่าจะพบพจนานุกรมย่อยทั่วไปจากนั้นแต่ละคำจะถูกสร้างขึ้นใหม่
โฟกัส:
ตามจริงแล้วฉันอยู่ในโรงเรียนโดยมุ่งเน้นไปที่สิ่งอื่น ๆ นอกเหนือจากรหัสดังนั้นฉันจึงรู้สึกไม่สบายใจ ฉันกำลังใช้เทคนิคที่น้อยกว่าอุดมคติสองสามข้อดังนั้นคำแนะนำใด ๆ ที่ยินดีต้อนรับ:
ฟังก์ชันการค้นหา
_extract_strings
ใช้ประโยชน์จากการเรียกซ้ำเพราะดูเหมือนว่าจะเป็นปัญหาที่เจ็บปวดในการแก้ไขซ้ำ ๆ หากฉันพลาดวิธีอื่นที่ชัดเจนฉันจะขอบคุณเคล็ดลับที่นั่นในฟังก์ชันเรียกซ้ำฉันใช้สตริงเพื่อติดตามคำว่า "จนถึงตอนนี้" และส่งสำเนาที่ต่อกันไปให้เด็ก ๆ เพื่อให้พวกเขาใช้ เดิมทีฉันใช้รายการดังนั้นฉันจึงทำได้
append
โดยไม่ต้องสร้างออบเจ็กต์ใหม่ทุกครั้ง แต่การแบ่งปันรายการที่ไม่แน่นอนระหว่างการเรียกซ้ำพิสูจน์แล้วว่าเป็นปัญหา ฉันยังส่งคืนเฉพาะตอนจบจากฟังก์ชันการค้นหาจากนั้นสร้างคำเต็มในfind_matching
. สิ่งนี้จำเป็นstring +
สำหรับทุกสตริงที่พบซึ่งไม่ดีนัก
ฟังก์ชันเหล่านี้ทำงานได้รวดเร็วอย่างน่าประหลาดใจ ฉันกำลังจะติดตั้งระบบแคชโหลดจากดิสก์เมื่อเริ่มต้นเพื่อหลีกเลี่ยงความจำเป็นในการสร้างตารางใหม่อยู่ตลอดเวลา แต่มันเร็วมากจนดูเหมือนไม่คุ้มค่า ด้วยเหตุนี้ข้อกังวลของฉันทั้งสองข้อข้างต้นอาจอยู่ภายใต้ "การเพิ่มประสิทธิภาพก่อนเวลาอันควร" แต่ฉันยังคงต้องการคำแนะนำเกี่ยวกับสิ่งเหล่านี้หรือสิ่งอื่นใดตั้งแต่สไตล์ไปจนถึงแนวทางปฏิบัติที่ดีที่สุด
รหัส:
import os
from typing import List, Iterable, Dict
_TERMINATOR = "\0"
_PATH_KEY = "PATH"
_PATH_DELIM = ":"
Table = Dict[str, "Table"]
def _get_paths() -> List[str]:
return os.environ[_PATH_KEY].split(_PATH_DELIM)
def _find_filenames_in(paths: List[str]) -> Iterable[str]:
return (fname
for path in paths
for _, _, fnames in os.walk(path)
for fname in fnames)
def _add_string(table: Table, string: str) -> None:
term_string = string + _TERMINATOR
cur_level = table
for c in term_string:
if c not in cur_level:
cur_level[c] = {}
cur_level = cur_level[c]
def make_lookup_table_from(strings: Iterable[str]) -> Table:
table = {}
for string in strings:
_add_string(table, string)
return table
def make_lookup_table_from_path() -> Table:
paths = _get_paths()
fnames = _find_filenames_in(paths)
return make_lookup_table_from(fnames)
def _extract_strings(table: Table) -> Iterable[str]:
acc = []
def rec(cur_path: str, cur_level: Table):
for char, child in cur_level.items():
if char == _TERMINATOR:
acc.append(cur_path)
else:
rec(cur_path + char, child)
rec("", table)
return acc
def find_matching(table: Table, string: str) -> Iterable[str]:
cur_level = table
for c in string:
try:
cur_level = cur_level[c]
except KeyError:
return []
return [string + end for end in _extract_strings(cur_level)]
คำตอบ
คุณสามารถใช้
dict.setdefault
แทนการปรับเปลี่ยน Trie ตามเงื่อนไข สิ่งนี้มีประโยชน์ในการค้นหาคีย์เพียงครั้งเดียวเมื่อเทียบกับสูงสุด 3 ครั้งด้วยรหัสปัจจุบันของคุณฉันไม่ใช่แฟนของคำศัพท์ของคุณ:
table
ทำให้ฉันคิดว่าอาร์เรย์ 2d มากกว่าต้นไม้- ฉันไม่ต้องการที่จะ
node
cur_level
- อะไร
c
หมายถึง? - ทำไมไม่เรียกมัน
_add_value
?
def _add_value(root: Table, string: str) -> None:
node = root
for char in string + _TERMINATOR:
node = node.setdefault(char, {})
ใน
_extract_strings
ฉันจะย้ายacc = []
ตามนิยามฟังก์ชันดังนั้นรหัสจึงไม่อยู่ในตำแหน่งทั้งหมด-
ในฟังก์ชันเรียกซ้ำฉันใช้สตริงเพื่อติดตามคำว่า "จนถึงตอนนี้" และส่งสำเนาที่ต่อกันไปให้เด็ก ๆ เพื่อให้พวกเขาใช้ เดิมทีฉันใช้รายการดังนั้นฉันจึงสามารถต่อท้ายได้โดยไม่ต้องสร้างวัตถุใหม่ทุกครั้ง แต่การแบ่งปันรายการที่ไม่แน่นอนระหว่างการเรียกซ้ำได้รับการพิสูจน์แล้วว่าเป็นปัญหา ฉันยังส่งคืนเฉพาะตอนจบจากฟังก์ชันการค้นหาจากนั้นสร้างคำเต็มใหม่ใน find_matching สิ่งนี้จำเป็นต้องใช้สตริง + สำหรับทุกสตริงที่พบซึ่งไม่ดีนัก
เมื่อได้ค่าหนึ่งรหัสของคุณจะทำงานใน\$O(l^2)\$ที่ไหน\$l\$คือความยาวสูงสุดของสตริง เนื่องจากแต่ละรายการ
cur_path + char
เป็น\$O(l)\$การดำเนินการและคุณทำมัน\$l\$ ครั้ง.ด้วยอัลกอริทึมปัจจุบันฉันขอแนะนำให้ทำตามวิธีการ 'eh, screw it' และขอให้มีความสุขที่เร็วพอ ในฐานะที่ตนเองจัดการกับสแต็คเป็นไม่สนุก
ส่วนตัวผมไม่ได้เป็นแฟนของ
acc.append
ผมใช้แทนและyield
yield from
def _extract_strings(table: Table) -> Iterator[str]: def rec(cur_path: str, cur_level: Table): for char, child in cur_level.items(): if char == _TERMINATOR: yield cur_path else: yield from rec(cur_path + char, child) return rec("", table)
-
ฟังก์ชันการค้นหา _extract_strings ใช้ประโยชน์จากการเรียกซ้ำเพราะดูเหมือนว่าจะเป็นปัญหาที่เจ็บปวดในการแก้ไขซ้ำ ๆ หากฉันพลาดวิธีอื่นที่ชัดเจนฉันจะขอบคุณเคล็ดลับที่นั่น
ในขณะที่การสร้างสแตกด้วยตนเองนั้นเป็นไปได้ แต่ก็ไม่ง่ายเลย เนื่องจาก trie ไม่น่าจะเกินขีด จำกัด 1,000 stack ของ Python คุณอาจเพิกเฉยต่อสิ่งนี้ได้
อย่างที่เคยสัมผัสมาก่อนเมื่อสร้างสแต็กเราสามารถสร้างผลลัพธ์ในเวลาเดียวกันได้อย่างง่ายดายโดยเปลี่ยน\$O(l^2)\$ประสิทธิภาพเป็นเพียง\$O(l)\$.อย่างไรก็ตามคุณควรจะเห็นว่านี่เป็นสิ่งที่น่ารังเกียจ ฉันไม่คิดว่าจะมีใครอยากรักษาสิ่งนี้
def _extract_strings(table: Table) -> Iterator[str]: stack = [iter(table.items())] stack_value = [] while stack: try: key, value = next(stack[-1]) except StopIteration: stack.pop() if stack_value: stack_value.pop() continue if key == '\0': yield ''.join(stack_value) stack_value.append(key) stack.append(iter(value.items())) table = { 'b': {'a': {'r': {'\0': {}}, 'z': {'\0': {}}}}, 'f': {'o': {'o': {'\0': {}}}}, } for path in _extract_strings(table): print(path)
ฉันไม่ได้คลั่งไคล้สายว่างของคุณมากมาย ดูเหมือนสุ่มและไม่จำเป็น
ทั้งสามคนจะอธิบายได้ดีกว่าในชั้นเรียน ชั้นเรียนแม้จะไม่มีน้ำตาล แต่ก็ทำให้เข้าใจรหัสของคุณได้ง่ายขึ้นเพราะคุณไม่ต้องคิดว่า "คืออะไร
_add_string
" และ "ฉันจะจัดการอย่างไรtable
"
ในช่วงหลายปีที่ผ่านมาฉันได้ลองเขียนบางครั้งพวกเขาอาจช่วยได้หากคุณตัดสินใจเลือกเรียนtrie = Trie() trie.add('foo') trie.add('bar') trie.add('baz') # Could use the following to add instead if you need a value # trie['foo'] = ??? key = 'ba' for value in trie[key]: print(key + value)
-
แผนจนถึงตอนนี้จะมีการเรียก
make_lookup_table_from_path
หนึ่งครั้งเมื่อโหลดเชลล์บันทึกตารางในตัวแปรนอกลูปหลักจากนั้นทำการค้นหาบนตารางที่บันทึกไว้ (ยิ่งฉันเขียน "ตาราง" มากเท่าไหร่ฉันก็ยิ่งมากขึ้นเท่านั้น m ตระหนักดีว่านั่นอาจไม่ใช่คำที่ถูกต้อง)การใช้ Trie นี่เป็นทางออกที่ดี
หากคุณกำลังสร้างตารางใหม่ทุกครั้งที่คุณโทรหาfind_matching
วิธีง่ายๆstr.startswith
ก็น่าจะทำได้ตามระยะทางหลายไมล์
โดยรวม
รูปแบบรหัสของคุณดูแปลก ๆ เล็กน้อย แต่อย่างอื่นก็ดีนะ ฉันขอแนะนำให้ใช้ชั้นเรียนเป็นส่วนใหญ่