ค้นคำหลายคำในประโยคโดยอนุญาตให้สลับตำแหน่งคำได้
18-08-2022 16:39:38
สมมุติว่าเรามีรายการข้อความจำนวนมาก แล้วต้องการค้นข้อความที่มีคำว่า "หนึ่ง", "สอง", และ "สาม" โดยคำเหล่านี้จะอยู่ในตำแหน่งใดในข้อความก็ได้ ไม่จำเป็นต้องติดกัน และไม่จำเป็นต้องเรียงลำดับกัน เราจะทำอย่างไร
โดยปกติ ปัญหาแบบนี้จะใช้กลไกที่เรียกว่า regular expression (regex) ซึ่งเป็นเหมือนภาษาหนึ่งที่ทำให้เรากำหนดได้ว่าเราต้องการ match ข้อความด้วย pattern หรือเงื่อนไขอย่างไร เช่นในกรณีนี้ เราก็จะเขียน regex ว่า
หนึ่ง.*สอง.*สาม
ซึ่งแปลว่า ให้ค้นข้อความที่มีคำว่า "หนึ่ง" ตามด้วย "สอง" ตามด้วย "สาม" ตามลำดับ โดยระหว่างแต่ละคำอาจมีอะไรคั่นกลาง (หรือไม่มี) ก็ได้ แต่สูตร regex นี้ไม่อนุญาตให้ค้นสลับที่ได้ เช่นถ้าประโยคคือ "สองกับสามกับหนึ่ง" ก็จะค้นไม่พบ เพราะ regex กำหนดว่าจะพบก็ต่อเมื่อ "หนึ่ง" มาก่อน "สอง" และมาก่อน "สาม" เป็นลำดับไป
วิธีการคือ ต้องสร้าง permutation ที่เป็นไปได้ทั้งหมดของสามคำนี้ แล้วเชื่อมด้วยเงื่อนไข "หรือ" ซึ่งในภาษา regex คือ | ดังนั้น เราต้องสร้าง regex ดังนี้:
หนึ่ง.*สอง.*สาม|หนึ่ง.*สาม.*สอง|สอง.*หนึ่ง.*สาม|สอง.*สาม.*หนึ่ง|สาม.*หนึ่ง.*สอง|สาม.*สอง.*หนึ่ง
แน่นอนว่าปัญหาจะเกิดขึ้นทันที คือมันซับซ้อนมาก เพราะมี permutation จำนวนมากที่ต้องเขียน หากเรามีคำหรือรูปแบบที่ต้องการ match จำนวนมาก ก็จะเสียเวลาเขียน regex เยอะมาก
ปัญหานี้เราเจอมานานและยังไม่มีโอกาสได้แก้ จนถึงวันนี้ จึงตัดสินใจเขียน function สร้าง regex จาก "ภาษาธรรมชาติ" โดยกำหนดให้ input อยู่ในรูปแบบที่คนทั่วไปเขียนได้ง่าย เช่น 'หนึ่ง+สอง+สาม, ห้า+สี่, ทดสอบ' เป็นต้น แล้วแปลงเป็น regex ที่มี permutation ครบทั้งหมด
กลไกของ function นี้ก็มีหลายขั้น ยุ่งยากพอสมควร หากใครสนใจลองไล่อ่านกันเองได้ แต่ถ้าจะให้สรุปสั้นๆ ก็เป็นประมาณนี้:
- แปลงกลุ่มเงื่อนไขที่คั่นด้วย comma ให้เป็น list แล้วแต่ละ element ให้ตัด space ออก
- วนลูปใน list นี้ โดยตั้งเงื่อนไขว่าถ้าเจอเครื่องหมายบวก + ให้ดำเนินการ permutation โดยแยกแต่ละคำให้กลายเป็น list element จากนั้นใช้เครื่องมือ itertools > permutations สร้าง list ใหม่ที่เป็น permutation ทั้งหมด แล้วเชื่อมแต่ละคำภายในแต่ละ permutation ด้วย .* ส่วนแต่ละ permutation ก็เชื่อมด้วย |
- สำหรับเงื่อนไขที่เป็นคำโดดๆ ก็เอามาเชื่อมกับผลลัพธ์จากข้อ 2 ด้วย | ก็จะได้ permutation ทั้งหมดตามที่ต้องการ
Application แรกที่จะใช้สูตรนี้ จะเป็นการค้นหา hate speech จากข้อความใน social media ซึ่งอาจจะทำให้เราสามารถสร้างระบบ early warning ได้ จากการค้นหารูปแบบข้อความที่เข้าข่าย hate speech