Tree Traversals และ Anagrams ใน Python

บทความนี้มีลิงค์พันธมิตร ดู การเปิดเผยข้อมูลในเครือ ของฉันสำหรับข้อมูลเพิ่มเติม

ฉันรู้ว่ามันเป็นแค่ความบังเอิญของภาษา แต่ความจริงที่ว่าคุณสามารถจัดเรียงตัวอักษรใน “ดวงตา” ใหม่เป็น “พวกเขาเห็น” ได้ให้ความรู้สึก… มหัศจรรย์

ตั้งแต่ฉันยังเป็นเด็ก ฉันชอบแอนนาแกรม ดังนั้น ฉันคิดว่าฉันจะพยายามสร้างตัวสร้างแอนนาแกรมใน Python มันกลายเป็นโปรเจ็กต์วันหยุดสุดสัปดาห์ที่สนุกสนานด้วยการข้ามต้นไม้และการเรียกซ้ำ

นี่คือสิ่งที่ฉันคิดขึ้นมา

วิธีตรวจสอบว่าสองสตริงเป็นแอนนาแกรมหรือไม่

string1 เป็นแอนนาแกรมของ string2 หากอักขระใน string1 เป็นการจัดเรียงอักขระใหม่ใน string2

ลำดับของตัวละครไม่สำคัญหรอก สิ่งสำคัญคือจำนวนอักขระแต่ละตัวใน string1 เท่ากับจำนวนอักขระแต่ละตัวใน string2 หากอักขระแต่ละตัวปรากฏจำนวนครั้งเท่ากันในแต่ละสตริง สตริงทั้งสองจะเป็นแอนนาแกรมของกันและกัน

collections.Counter ของ Python สามารถคำนวณสิ่งนี้:

 from collections import Counter string1 = "the eyes" string2 = "they see" Counter(string1) # Counter({ # 'e': 3, # 't': 1, # 'h': 1, # ' ': 1, # 'y': 1, # 's': 1 # }) Counter(string1) == Counter(string2) # True ✅

เห็นสตริงว่างนั้น ' ' ในวัตถุ Counter หรือไม่ นั่นเป็นปัญหา “โรงละคร” และ “น้ำตา” เป็นแอนนาแกรม แม้ว่าอันหนึ่งจะมีที่ว่างและอีกอันไม่มี แอนนาแกรมไม่คำนึงถึงตัวพิมพ์เล็กและตัวพิมพ์ใหญ่ พวกเขาอาจมีเครื่องหมายวรรคตอนต่างกัน เช่น “vitalise” และ “IT’S ALIVE!”

โซลูชันที่มีประสิทธิภาพจำเป็นต้องคำนึงถึงทั้งหมดนี้ ดังนั้น collections.Counter จะไม่ตัดออกหากไม่มีการประมวลผลล่วงหน้า:

 string1 = "vitalise" string2 = "IT'S ALIVE!" Counter(string1) == Counter(string2) # False ❌

เช่นเดียวกับปัญหาส่วนใหญ่ มีหลายวิธีในการแก้ปัญหานี้

ฉันต้องการโซลูชันที่เข้าใจง่ายและเปลี่ยนแปลงได้ง่ายในกรณีที่ไม่สามารถจัดการได้ทุกกรณี ฉันใช้เมธอด string .translate() ซึ่งแทนที่อักขระแต่ละตัวในสตริงตามพจนานุกรมการแปล อักขระที่แมปกับ None จะถูกลบออกจากสตริง นอกจากนี้ ฉันสามารถสร้างพจนานุกรมการแปลด้วย str.maketrans() ได้อย่างง่ายดาย

สิ่งนี้ทำให้ฉันควบคุมวิธีการประมวลผลสตริงอย่างละเอียดก่อนที่จะถูกส่งไปยัง Counter() :

 from collections import Counter from string import punctuation, whitespace from typing import Callable def process(string_: str) -> str: chars_to_remove = punctuation + whitespace translation = str.maketrans("", "", chars_to_remove) return string_.translate(translation).lower() def are_anagrams( string1: str, string2: str, process: Callable = process ) -> bool: processed1 = process(string1) processed2 = process(string2) return Counter(processed1) == Counter(processed2)

ควรใช้ .casefold() แทน .lower() ในฟังก์ชัน process() แต่โดยรวมแล้ว สิ่งนี้ทำให้เป็นโซลูชันที่แข็งแกร่ง เข้าใจง่าย หากคุณทราบเกี่ยวกับ Counter , .translate() และ str.maketrans() และง่ายต่อการสลับฟังก์ชันการประมวลผลหากจำเป็น

แล้วการค้นหาแอนนาแกรมสำหรับสตริงเฉพาะล่ะ

วิธีสร้างแอนนาแกรม

ยากกว่าการตรวจสอบว่าสองสตริงเป็นแอนนาแกรมของกันและกันหรือไม่

การสร้างสตริงใหม่ที่เป็นไปได้ทั้งหมดนั้นไม่เพียงพอ คุณต้องแทรกช่องว่างและเครื่องหมายวรรคตอนในตำแหน่งที่เหมาะสม คำที่เป็นผลลัพธ์ในสตริงจะต้องเป็นคำในพจนานุกรมจริง

เราต้องการวิธีสร้างคำที่ใช้ตัวอักษรจากสตริงได้อย่างมีประสิทธิภาพ

การแก้ปัญหาบนกระดาษ

กันปัญหาในการรับรายการคำศัพท์และเริ่มง่าย ๆ :

 eyes the they see sea

กระบวนการเป็นดังนี้:

1. เขียนวลีที่จะสร้างแอนนาแกรม เช่น “ดวงตา”
2. เลือกจดหมายจากวลี (พูดว่า “t”) และสแกนรายการเพื่อหาคำที่ขึ้นต้นด้วยตัวอักษรนั้น (คำ = “the” และ “they”) ขีดฆ่าตัวอย่างหนึ่งของตัวอักษรในวลี และเขียนจดหมายนั้นเป็นอักษรตัวแรกของแอนนาแกรม (anagram = “t”)
3. เลือกตัวอักษรจากวลีที่ยังไม่ได้ขีดฆ่า (พูดว่า “h”) และกรองคำที่เลือกในขั้นตอนสุดท้ายเป็นตัวอักษรที่ 2 เป็นตัวอักษรใหม่ที่คุณเลือก (words = “the” และ ” พวกเขา”). ขีดฆ่าตัวอักษรในวลีและเพิ่มลงในแอนนาแกรมของคุณ (anagram = “th”)
4. ดำเนินการตามขั้นตอนนี้ต่อไปในการเลือกตัวอักษรที่ไม่ได้ใช้และกรองรายการคำ เมื่อคุณไปถึงจุดสิ้นสุดของคำ ให้ตรวจสอบว่าวลีที่คุณสร้างขึ้นนั้นเป็นแอนนาแกรมของวลีดั้งเดิมหรือไม่ ถ้าใช่ แสดงว่าคุณทำเสร็จแล้ว ถ้าไม่ ให้เริ่มใหม่ด้วยรายการคำทั้งหมดแต่ใช้เฉพาะตัวอักษรที่ยังไม่ได้ขีดฆ่า
5. ทำซ้ำขั้นตอนทั้งหมดโดยใช้ตัวอักษรเริ่มต้นที่แตกต่างจากวลี

หากคุณปฏิบัติตามอัลกอริทึมนี้ทีละขั้นตอนในรายการคำเล็กๆ ด้านบน คุณจะพบกับสี่แอนนาแกรม:

• ตา
• ตา
• พวกเขาเห็น
• เห็นพวกเขา

แน่นอน “ดวงตา” คือวลีที่คุณเริ่มด้วย ไม่เป็นไร. เพียงแค่ทิ้งมัน

จะดีแค่ไหนถ้า แทนที่จะสแกนรายการทั้งหมดเพื่อหาคำทั้งหมดที่ขึ้นต้นด้วยตัวอักษร T เราสามารถข้ามไปยังคำเหล่านั้นได้โดยตรง หรือข้ามไปที่คำทั้งหมดที่ขึ้นต้นด้วย TH? หรือเริ่มต้นด้วย THE?

ดูเหมือนว่าเราต้องการตารางแฮช!

สิ่งที่เรา ต้องการ คือตารางแฮช ของ ตารางแฮช

ตารางแฮชของตารางแฮชเป็นวิธีหนึ่งในการแสดงต้นไม้ และถ้าคุณหยุดและคิดเกี่ยวกับมัน วิธีที่ฉันอธิบายไว้สำหรับการสร้างแอนนาแกรมให้ความรู้สึกเหมือนการค้นหาในเชิงลึกเป็นอันดับแรก นั่นเป็นเงื่อนงำที่ยิ่งใหญ่สำหรับวิธีการใช้อัลกอริทึม

และ Python มีทุกส่วนที่เราต้องการ

สร้างต้นไม้แห่งพจนานุกรม

ต้นไม้ที่เราจะสร้างจะมีลักษณะดังนี้:

พจนานุกรม Python เป็นตารางแฮช ดังนั้นจึงเป็นตัวเลือกที่เป็นธรรมชาติสำหรับพื้นฐานของแผนผังของเรา คีย์สำหรับพจนานุกรมแต่ละชุดคือสตริงที่มีตัวอักษรตัวเดียว และค่าต่างๆ จะเป็นพจนานุกรมมากกว่า เราจำเป็นต้องรู้เมื่อเราอยู่ท้ายคำ ดังนั้นเราจะทำเครื่องหมายสถานที่เหล่านั้นด้วยพจนานุกรม {" ": {}}

ต้นไม้พจนานุกรมสำหรับคำว่า eyes, the, they, see และ sea มีลักษณะดังนี้:

 {'e': {'y': {'e': {'s': {' ': {}}}}}, 's': {'e': {'a': {' ': {}}, 'e': {' ': {}}}}, 't': {'h': {'e': {' ': {}, 'y': {' ': {}}}}}}

แต่จะสร้างพจนานุกรมแบบนี้ได้อย่างไร?

การสังเกตที่สำคัญคือคุณสามารถเพิ่มคำลงในพจนานุกรมแบบเรียกซ้ำได้ เริ่มต้นด้วยพจนานุกรมเปล่า สำหรับแต่ละคำ ให้ปิดตัวอักษรตัวแรก – เรียกว่า char หาก char เป็นกุญแจสำคัญในพจนานุกรม ให้คว้าคุณค่าของมันไว้ มิฉะนั้น ให้ตั้งค่าคีย์ char ร์ในพจนานุกรมด้วยพจนานุกรมเปล่าสำหรับค่าของมัน จากนั้นทำซ้ำขั้นตอนโดยใช้พจนานุกรมที่แมปกับ char และคำโดยไม่มีอักขระตัวแรก

สมมติ word ไม่มีช่องว่างและตรึงสตริง " " ต่อท้าย เพื่อให้เราได้รับพจนานุกรมเทอร์มินัลถูกต้อง

นี่คือรหัส:

 from typing import Iterable def add_word(tree: dict, word: str) -> None: if word != "": char = word[0] branch = tree.get(char, {}) tree[char] = branch _add_word(branch, word[1:]) def build_word_tree(words: Iterable[str]) -> dict: word_tree = {} for word in words: add_word(word_tree, word + " ") return word_tree

การเรียกซ้ำนั้นดีเพราะสามารถอธิบายกระบวนการซ้ำๆ ได้กระชับ แต่อาจเป็นเรื่องยากที่จะเข้าใจว่าอัลกอริธึมแบบเรียกซ้ำทำอะไรโดยไม่ต้องให้เหตุผลผ่านขั้นตอนต่างๆ ด้วยมือ เอกสารที่มีตัวอย่างที่ดีสามารถช่วยให้ผู้อ่าน (รวมถึงตัวตนในอนาคตของคุณ) เข้าใจฟังก์ชันแบบเรียกซ้ำ

ตอนนี้เรามีต้นไม้ที่จะใช้งานแล้ว เราสามารถเริ่มสร้างแอนนาแกรมได้

สำรวจต้นไม้เพื่อสร้างแอนนาแกรม

คุณสามารถใช้อัลกอริธึมแอนนาแกรมเพื่อเดินข้ามโหนดในแผนผังคำได้

เราเลือกโหนดเริ่มต้น – หนึ่งในอักขระในวลีที่เราต้องการให้แอนนาแกรม – และทำเครื่องหมายโหนดนั้นตามที่เข้าชมในอาร์เรย์ จากนั้นย้ายไปที่กิ่งในต้นไม้ที่รูทที่โหนดนั้น ทำซ้ำไปเรื่อย ๆ จนกว่าคุณจะไปที่อักขระทั้งหมดในวลีหรือถึงจุดสิ้นสุดของคำ ซ้ำเติม!

โดยพื้นฐานแล้วมันเป็นอัลกอริธึมการค้นหาเชิงลึก ยกเว้นว่าโหนดที่สามารถเดินไปถึงนั้นถูกจำกัดโดยโหนดในต้นไม้และอักขระในวลีที่ยังไม่ได้เข้าชม

สิ่งนี้ถูกจับในรหัส Python ต่อไปนี้:

 from typing import Generator def walks( tree: dict, filter_: Callable, _visited: tuple = () ) -> Generator: if tree == {}: yield _visited else: for node in filter_(tree, _visited): yield from walks( tree[node], filter_, (*_visited, node) )

filter_() ควรคืนค่า tuple ของโหนดที่สามารถเดินไปได้ มีความแตกต่างกันเล็กน้อยในการค้นหาแอนนาแกรม เราจะพูดถึงเรื่องนั้นในอีกสักครู่และระงับการกำหนดฟังก์ชันตัวกรองในตอนนี้

เรายังดำเนินการตามขั้นตอนสำหรับอัลกอริทึมแอนนาแกรมไม่เสร็จ

walks() ให้ผลลัพธ์ tuples ของโหนดที่เยี่ยมชมโดยการเดิน – อักขระจากวลีในกรณีนี้ – แต่การเดินจะสิ้นสุดทันทีที่ถึงจุดสิ้นสุดของคำ

ในการสร้างแอนนาแกรมหลายคำ คุณต้องวนไปรอบๆ และเดินต่อจากรากต้นไม้ต่อไป ฉันเรียกสิ่งนี้ว่า “การเดินไปรอบ ๆ” ต้นไม้ คุณเดินไปรอบ ๆ ไปเรื่อย ๆ รวบรวมคำพูดจนกว่าการเดินจะเสร็จสิ้น

นี่คือรหัส:

 def walk_around( tree: dict, done: Callable, filter_: Callable, _visited: tuple = (), ) -> Generator: for walk in walks(tree, filter_, _visited): if done(walk): yield walk else: yield from walk_around( tree, done, filter_, walk )

เราจำเป็นต้องใช้ฟังก์ชัน done และ filter เพื่อส่งผ่านไปยัง walk_around() ซึ่งทั้งสองอย่างนี้ขึ้นอยู่กับวลีที่เรากำลังสร้างแอนนาแกรม

การเดินจะกระทำเมื่อสตริงของอักขระที่เข้าชมในการเดินเป็นแอนนาแกรมของวลี เรารู้วิธีทำเช่นนั้นแล้ว! เราสามารถใช้ are_anagrams() ได้:

 def done(phrase: str, walk: tuple) -> bool: return are_anagrams(phrase, "".join(walk))

ตอนนี้เราต้องกำหนด filter_()

ฉันบอกว่ามีความแตกต่างกันนิดหน่อยในเรื่องนี้

ในแต่ละขั้นตอนของการเดิน เราต้องขยับไปที่ตัวละครในวลีที่เรายังไม่เคยไป หรือเครื่องหมายวรรคตอน เนื่องจากเราต้องการรวมคำต่างๆ เช่น การหดตัว โอ้ และเรายังสามารถย้ายไปยังอักขระ " " ได้ด้วย เนื่องจากเรารู้ว่าเราอยู่ท้ายคำ

เราสามารถแสดงกฎเหล่านี้ได้อย่างหมดจดโดยใช้ set :

 def filter_( phrase: str, tree: dict, _visited: tuple ) -> tuple: remaining = set(Counter(phrase) - Counter(_visited)) _punctuation = set(punctuation) end_of_word = {" "} allowed = remaining | _punctuation | end_of_word nodes = set(tree.keys()) anagram_nodes = nodes.intersection(allowed) return tuple(anagram_nodes)

ตัว Counter ทำให้ง่ายต่อการคำนวณอักขระในวลีที่ยังไม่เคยเข้าชม

การลบตัว Counter ออกจากตัวนับอื่นจะคืนค่าตัว Counter พร้อมจำนวนที่หักออก อักขระที่นับเป็นศูนย์จะถูกลบออก ตัวอย่างเช่น Counter("tea") - Counter("e") ส่งคืน Counter({'t': 1, 'a': 1})

The | เป็น โอเปอเรเตอร์การรวมพจนานุกรม ที่มีตั้งแต่ Python 3.9

เรามีทุกส่วนในการเขียนตัวสร้างแอนนาแกรม:

 from functools import partial def anagrams(phrase: str, words: Iterable) -> Generator: tree = build_word_tree(words) _done = partial(done, phrase) _filter = partial(filter_, phrase) for walk in walk_around(tree, _done, _filter): anagram = "".join(walk).rstrip() if anagram != phrase: yield "".join(walk).rstrip()

functools.partial() ใช้ที่นี่เพื่อ “กรอก” พารามิเตอร์ phrase ของฟังก์ชัน done() และ filter_() เราต้องทำสิ่งนี้เพราะพารามิเตอร์ done และ filter_ ของ walk_around() คาดหวังฟังก์ชันที่ไม่มีพารามิเตอร์ phrase ช่องว่างในแอนนาแกรมจะถูกลบออกด้วย .rstrip() เนื่องจากการเดินที่สร้างโดย walk_around() ลงท้ายด้วยช่องว่าง

ลองใช้ anagrams() เพื่อหมุนรายการคำเล็ก ๆ :

 words = ["eyes", "the", "they", "see", "sea"] phrase = "the eyes" for anagram in anagrams(phrase, words): print(anagram.rstrip()) # eyes the # they see # see they

เฮ้ มันได้ผล!

การทดสอบชุดคำขนาดใหญ่

หากคอมพิวเตอร์ของคุณมีระบบปฏิบัติการที่คล้ายกับ Unix แสดงว่าคุณมีรายการคำจำนวนมากในขณะนี้

ในเครื่องส่วนใหญ่ มีไฟล์ words อยู่ที่ /usr/share/dict/words หรือ /usr/dict/words เป็นรายการคำในพจนานุกรมที่คั่นด้วยการขึ้นบรรทัดใหม่ หากคุณมีเครื่อง Windows หรือไม่มีไฟล์ words คุณสามารถค้นหา tarball สำหรับไฟล์ในภาษาของคุณบนเว็บไซต์ GNU

มาลองดูกัน:

 from pathlib import Path words_path = Path("/usr/share/dict/words") words = words_path.read_text() # The words file ends with a blank line so we # need to remove trailing whitespace words = words.lower().strip().split("\n") phrase = "tea" for anagram in anagrams(phrase, words): print(anagram) # ate # a te # aet # at e # ate # ae t # tae # ...

มันใช้งานได้ดี แต่ไฟล์ words มีตัวอักษรเดี่ยวและคำสองตัวอักษรเช่น “te” ที่เพิ่มเสียงให้กับแอนนาแกรมของเรา เราน่าจะทำความสะอาดมัน

มากรองคำบางคำที่เรารู้ว่าไม่ต้องการ:

 from string import ascii_lowercase SINGLE_LETTERS = set(ascii_lowercase) - {"a", "i"} TWO_LETTER_WORDS = {"te", "ae", "ea"} FORBIDDEN = SINGLE_LETTERS | TWO_LETTER_WORDS words_path = Path("/usr/share/dict/words") words = words_path.read_text() words = words.lower().strip().split("\n") words = (word for word in words if word not in FORBIDDEN) phrase = "tea" for anagram in anagrams(phrase, words): print(anagram) # eat # eta # ate # tae

สิ่งนี้ทำให้เราได้ผลลัพธ์ที่ดีขึ้นอย่างแน่นอน สำหรับโปรแกรมสร้างแอนนาแกรมที่ดีจริงๆ คุณจะต้องใช้เวลาในการดูแลคำศัพท์ และไฟล์ words ไม่จำเป็นต้องเป็นชุดของคำที่ดีที่สุดในการเริ่มต้น เนื่องจากไม่มีการย่อใดๆ

คุณสามารถสร้างรายการคำศัพท์ที่น่าสนใจยิ่งขึ้นโดยใช้ เครื่องมือ SCOWL ของ aspell

มีความสุขในการล่าแอนนาแกรม!

---