เสิร์ชเอนจินที่สร้างด้วย Python เพียง 80 บรรทัด

 (alexmolas.com)
6 คะแนน โดย GN⁺ 2024-02-08 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • microsearch เป็น งานทำเล่นเพื่อการเรียนรู้ สำหรับทำความเข้าใจภายในของเสิร์ชเอนจินโดยตรง โดยคลาสเสิร์ชเอนจินแกนหลักมีไม่ถึง 80 บรรทัด แต่เมื่อรวม crawler, API และ HTML template แล้ว ตัวโปรเจ็กต์จะมีขนาดใหญ่กว่านั้น
  • โดยมีฉากหลังเป็นปัญหาที่เว็บไซต์และบล็อกขนาดเล็กมักถูกค้นพบได้ไม่ดีนักในเสิร์ชเอนจินขนาดใหญ่ จึงเก็บบทความจาก RSS feed จำนวน 642 รายการมาสร้างข้อมูลสำหรับการค้นหา
  • ใช้ การ crawl แบบ asynchronous บนพื้นฐาน asyncio จนลดเวลารวบรวมข้อมูลจาก 20 นาทีเหลือ 20 วินาที และบันทึกเนื้อหาที่จัดระเบียบแล้วเป็นข้อมูล Parquet
  • การค้นหาทำงานบน inverted index ที่เชื่อมคำกับจำนวนครั้งที่ปรากฏในแต่ละ URL และใช้ BM25 ที่อิงตามเนื้อหาแทน PageRank ที่อิงตามลิงก์สำหรับการจัดอันดับผลลัพธ์
  • มี UI ด้วย FastAPI สำหรับช่องค้นหาและหน้าผลลัพธ์ แต่ยังไม่มีฟีเจอร์อย่าง query operator, n-gram indexing, query/document expansion และการทำดัชนีระหว่าง crawl

เป้าหมายและขอบเขตของ microsearch

  • microsearch คือ implementation ของเสิร์ชเอนจินภาษา Python ที่เปิดเผยไว้ใน GitHub repository
  • เป้าหมายไม่ใช่เสิร์ชเอนจินสำหรับใช้งาน production แต่เป็น ตัวอย่างแบบทำเล่นที่ใช้งานได้จริง เพื่อแสดงให้เห็นว่าเสิร์ชเอนจินทำงานภายในอย่างไร
  • เป้าหมายการค้นหาใกล้เคียงกับเว็บไซต์และบล็อกขนาดเล็กที่มักถูกค้นพบได้ไม่ดีนักในการแข่งขัน Google SEO
  • implementation แกนหลักของเสิร์ชเอนจินมีไม่ถึง 80 บรรทัด แต่เมื่อรวมโค้ดประกอบอย่าง data crawler, API และ HTML template แล้ว โปรเจ็กต์โดยรวมจะมีขนาดใหญ่กว่านั้น
  • งานนี้ถูกสร้างขึ้นระหว่างการทำความเข้าใจการทำงานของเสิร์ชเอนจินให้ลึกขึ้น ผ่านการใช้งาน Solr และ Lucene

Crawler ที่อิง RSS

  • เพื่อสร้างข้อมูลสำหรับค้นหา จึงทำการ crawl RSS feed ของบล็อกต่าง ๆ
  • feed ที่ใช้มีทั้งหมด 642 RSS feed
    • ประมาณ 100 รายการเป็นบล็อกที่ผู้เขียนอ่านเอง เช่น ML, data science, คณิตศาสตร์ เป็นต้น
    • ที่เหลืออีกราว 500 รายการนำมาจาก โปรเจ็กต์ surprisetalk blogs.hn
  • ขั้นตอนการ crawl คือดึง URL ของบทความจาก RSS feed แต่ละรายการ ดาวน์โหลด HTML ของบทความ แล้วจัดระเบียบข้อความเนื้อหา
  • การจัดระเบียบ HTML ใช้ BeautifulSoup เพื่อลบ script และ style แล้วแปลงเป็นข้อความพร้อมจัดการบรรทัดใหม่และช่องว่าง
  • ใช้ การ crawl แบบ asynchronous ด้วย aiohttp และ asyncio ทำให้เวลารันลดลงจาก 20 นาทีเหลือ 20 วินาที
  • ผลลัพธ์จะถูกสร้างเป็น DataFrame ที่เก็บ URL และเนื้อหาที่จัดระเบียบแล้ว ก่อนบันทึกลง output.parquet

โครงสร้าง inverted index

  • โครงสร้างข้อมูลแกนหลักอย่างแรกของเสิร์ชเอนจินคือ inverted index
  • inverted index จะ map คีย์เวิร์ดเข้ากับเอกสาร ทำให้ค้นหาได้รวดเร็วว่าคำใดปรากฏอยู่ในเอกสารไหนบ้าง
  • implementation ใช้ defaultdict ในรูปแบบ dict[str, dict[str, int]]
    • คีย์ชั้นนอกคือคำ
    • คีย์ชั้นในคือ URL
    • ค่าชั้นในคือจำนวนครั้งที่คำนั้นปรากฏในเอกสารของ URL นั้น
  • คลาส SearchEngine มี internal dictionary อยู่สองตัว
    • _index: เก็บจำนวนครั้งที่คำปรากฏในแต่ละ URL
    • _documents: เก็บเนื้อหาต้นฉบับแยกตาม URL
  • index(url, content) จะ normalize เนื้อหา แล้วแยกด้วยช่องว่าง จากนั้นเพิ่มจำนวนครั้งของแต่ละคำตาม URL
  • bulk_index() รับรายการ URL และเนื้อหาเพื่อทำดัชนีเอกสารหลายรายการพร้อมกัน
  • get_urls(keyword) จะ normalize คีย์เวิร์ดแล้วคืนค่า URL และจำนวนครั้งที่พบของคำนั้น

การ normalize สตริงและการค้นหาพื้นฐาน

  • การ normalize สตริงจะเปลี่ยนเครื่องหมายวรรคตอนเป็นช่องว่าง จัดการช่องว่างซ้ำ แล้วแปลงเป็นตัวพิมพ์เล็ก
  • เพื่อลดความต่างของตัวพิมพ์ใหญ่เล็ก Foo และ foo จึงถูกมองเป็นคีย์เวิร์ดเดียวกัน
  • เมื่อนำเอกสารตัวอย่างสองชิ้นมาทำดัชนี ผลการค้นหา foo จะคืนทั้งสองเอกสาร
    • Foo: Hello, World! My name is Foo!
    • Bar: Hello, World! My name is Bar, I'm not Foo!
  • ในขั้นนี้จะรู้เพียงว่าเอกสารมีคำค้นหรือไม่ และมีอยู่กี่ครั้งเท่านั้น ดังนั้นหากต้องการเรียงลำดับผลลัพธ์ก็ต้องมี ranking แยกต่างหาก

ตัวจัดอันดับ BM25

  • ใช้ BM25 สำหรับจัดอันดับผลการค้นหา
  • PageRank จัดอันดับเอกสารจากลิงก์ แต่ BM25 คำนวณคะแนนจากเนื้อหาเอกสาร
  • SearchEngine มีพารามิเตอร์เริ่มต้นสำหรับการคำนวณ BM25 คือ k1=1.5, b=0.75
  • คลาสนี้มีพร็อพเพอร์ตีที่จำเป็นต่อการคำนวณ ranking
    • posts: รายการ URL ที่ถูกทำดัชนีแล้ว
    • number_of_documents: จำนวนเอกสารทั้งหมด
    • avdl: ความยาวเฉลี่ยของเอกสาร
  • idf(kw) ใช้คำนวณ inverse document frequency ของคีย์เวิร์ดหนึ่งคำ
    • จำนวนเอกสารทั้งหมด N
    • จำนวนเอกสารที่มีคีย์เวิร์ดนั้น n_kw
    • ใช้สูตร log((N - n_kw + 0.5) / (n_kw + 0.5) + 1)
  • bm25(kw) จะคำนวณคะแนน BM25 สำหรับแต่ละ URL ที่มีคีย์เวิร์ดนั้น
  • search(query) จะ normalize query แล้วแยกเป็นคำ ก่อนรวมคะแนน BM25 ของแต่ละคำแยกตาม URL แล้วส่งกลับ
  • ในตัวอย่าง หากค้นหาเพียง foo เอกสาร Foo จะได้คะแนนสูงกว่า Bar แต่ถ้าค้นหา foo bar เอกสาร Bar จะได้คะแนนสูงกว่า

อินเทอร์เฟซ FastAPI

  • เสิร์ชเอนจินถูกเปิดให้ใช้งานผ่าน แอป FastAPI ขนาดเล็ก
  • แอปจะสร้างอินสแตนซ์ SearchEngine และเมื่อเริ่มทำงานจะอ่าน URL กับเนื้อหาจากข้อมูล Parquet แล้วทำดัชนีด้วย bulk_index()
  • route หลักมี 3 รายการ
    • /: render หน้าค้นหาและส่งรายการบทความที่ถูกทำดัชนีแล้ว
    • /results/{query}: ค้นหา query และแสดง URL 5 อันดับแรกในหน้าผลลัพธ์
    • /about: render หน้าแนะนำ
  • ผลลัพธ์จะถูกเรียงจากคะแนนมากไปน้อย แล้วเลือกเฉพาะ top-N URL
  • ทั้ง UI และ UX ยังมีพื้นที่ให้ปรับปรุงอีกมาก แต่การค้นหาทำงานได้รวดเร็วและผลลัพธ์ก็ไม่เลว

ฟีเจอร์ที่ยังขาดและข้อจำกัด

  • implementation นี้ยังขาดฟีเจอร์หลายอย่างที่มักคาดหวังจากเสิร์ชเอนจินจริง
  • ไม่มี query operator
    • ตัวอย่างเช่น ยังไม่รองรับการค้นหาแบบตัดบางคำออกเหมือน how to build a search engine -solr ของ Google
  • ไม่มี n-gram indexing
    • จึงยังไม่รองรับการค้นหาแบบหาเฉพาะเอกสารที่มีคำสองคำปรากฏตามลำดับ เช่น "search engine"
  • ไม่มี query หรือ document expansion
    • ต่อให้ค้นหา engine ก็จะไม่ดึงเอกสารที่มี engines มาให้โดยอัตโนมัติ
  • การ crawl และการทำดัชนียังแยกจากกัน
    • สามารถรวมให้เป็นรูปแบบที่ทำดัชนีได้ทันทีเมื่อรับเอกสารเข้ามา และทำให้กระบวนการนี้เป็น asynchronous ได้เช่นกัน

ขั้นถัดไป

  • โปรเจ็กต์นี้ช่วยให้เกิดความเข้าใจเชิงสัญชาตญาณมากขึ้นว่า Solr ทำงานภายในอย่างไร
  • อีกเรื่องที่ยืนยันได้คือโค้ดแบบ asynchronous ให้ผลอย่างมากกับงานที่เน้น IO
  • ขั้นถัดไปคือการเพิ่มความสามารถด้าน semantic search ให้กับเสิร์ชเอนจิน
  • ผู้เขียนได้ทดลองกับ embedding model และ ANN มาแล้ว และการนำความสามารถนั้นเข้าไปใน microsearch คือสิ่งที่จะทำต่อไป

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-02-08
ความคิดเห็นจาก Hacker News

  • อันนี้เจ๋งจริง กำลังทำ เสิร์ชเอนจิน BM25 ด้วย Pandas ที่ค่อนข้างเร็วสำหรับการทดสอบในเครื่อง: https://github.com/softwaredoug/searcharray
    อนึ่ง เหตุผลที่ใช้ Pandas คือ BM25 อย่างเดียวไม่พอ และอยากคำนวณปัจจัยอื่น ๆ เช่น ความสดใหม่·ความนิยม ด้วย pandas/numpy แล้วนำมาผสมกันได้ง่าย
    การค้นหาแบบวลี คือส่วนที่ยาก การจับคู่วลีมีกรณีขอบเยอะ และต้องพิจารณาสิ่งอย่าง slop ด้วย ต้องบีบอัดข้อมูลตำแหน่งให้ใช้หน่วยความจำน้อยที่สุดเท่าที่เป็นไปได้ด้วย: https://github.com/softwaredoug/searcharray/blob/main/searcharray/utils/roaringish.py

    • เคยจัดการ การจับคู่วลี ในโปรเจกต์ของเล่น: https://github.com/vasilionjea/lofi-dx/blob/main/test/search/inverted-search.test.ts#L140
      คิดว่าทดสอบไว้ค่อนข้างละเอียด แต่ถ้าได้ฟีดแบ็กก็คงดี ข้อมูลตำแหน่งใช้ delta encoding แล้วเข้ารหัสเป็น base36
    • สงสัยว่าการใส่ sentiment analysis ช่วยกับการประมวลผลวลีหรือเปล่า หรือกลับเป็นโทษกันแน่ วลีจัดการยาก และกำลังคิดอยู่ว่าจะทำอะไรได้บ้างเพื่อปรับปรุงประสิทธิภาพ
    • สงสัยว่ามาเจอบทความนี้แล้วคอมเมนต์ได้เร็วขนาดนี้ได้ยังไง อยากรู้ว่าใช้ เครื่องมือเฝ้าดูการค้นหา ที่ไล่ดูหน้าแรกเพื่อหาคีย์เวิร์ดที่สนใจอยู่หรือเปล่า หรือแค่บังเอิญ

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

  • ดู src/microsearch/engine.py แล้วมีโค้ดอย่าง SearchEngine.__init__(self, k1: float = 1.5, b: float = 0.75) แต่ไม่รู้เลยว่า k1 หรือ b คืออะไร และทั้งไฟล์ไม่มีคอมเมนต์สักบรรทัด
    เดี๋ยวนี้ คอมเมนต์ ไม่เป็นที่นิยมแล้วเหรอ? _documents ดูเหมือนคีย์จะเป็น URL และค่าจะเป็นเนื้อหาของ URL นั้น แต่อาจผิดก็ได้ มันน่าจะเป็นแหล่งเรียนรู้วิธีสร้างเสิร์ชเอนจินและนำไปต่อยอดได้ แต่คุณภาพโค้ดน่าเสียดายเพราะไม่ได้ทำเอกสารไว้

    • ส่วนนั้นอธิบายไว้ในบทความแล้ว และตัวบทความเองทำหน้าที่เป็น เอกสาร ของโค้ด ลิงก์ BM25 นำไปสู่พื้นฐานทางคณิตศาสตร์ และถ้าค้นพารามิเตอร์ BM25 เพิ่มอีกนิด ก็จะเจอบทความที่เกี่ยวข้องซึ่งพูดถึงวิธีเลือกค่าด้วย
    • ถ้าจะทำให้ชื่อบทความดึงดูดสายตา ก็ต้องลดจำนวนบรรทัดโค้ดให้มากที่สุด ;)
      พักเรื่องตลกไว้ก่อน โดยทั่วไปเห็นด้วยว่าเอกสารกับโค้ดอยู่ด้วยกันจะดีกว่า เพียงแต่กรณีนี้เป็นโปรเจกต์เพื่อการศึกษา เลยแยกโค้ดกับเอกสารออกจากกัน และเลือกทำเอกสารโค้ดในบล็อกโพสต์
    • ตอนนี้ใช้มือถือเลยดูละเอียดไม่ได้ แต่ k1 กับ b เป็น ค่าน้ำหนัก มาตรฐานที่ใช้ใน TF-IDF หรือ BM25 และที่นี่เป็นฝั่ง BM25
      ถ้ามีคอมเมนต์ก็คงมีประโยชน์ แต่สำหรับคนที่คุ้นกับปัญหานี้ ก็เป็นชื่อที่มองปุ๊บรู้ได้ทันทีเหมือนกัน
    • k1 กับ b เป็นพารามิเตอร์ปรับแต่งของ ฟังก์ชันจัดอันดับ BM25 ไม่ใช่ชื่อที่ผู้เขียนต้นฉบับตั้งขึ้นใหม่ แต่เป็นชื่อตัวแปรที่แทบทุก implementation และตำราใช้กัน
      สำหรับคนที่รู้จักสาขา information retrieval การตั้งชื่อว่า k1 กับ b กลับเป็นสิ่งที่ถูกต้องกว่า: https://en.wikipedia.org/wiki/Okapi_BM25
    • เห็นรูปแบบอย่าง a: float แล้วมักนึกถึงทอล์กของ Rich Hickey ที่ว่า “สิ่งที่ต้องการไม่ใช่ type แต่เป็นชื่อที่ดี” เสมอ
      ไม่ชอบแนวโน้มการใช้ชื่อตัวแปรตัวอักษรเดียวที่ไม่มีคำอธิบาย ซึ่งให้ความรู้สึกเหมือนมาจาก Go แล้วใช้ type system ในทางที่ผิดเหมือนเป็นเครื่องมือช่วยเรื่องชื่อจริง ๆ ชื่อสามารถสื่อ ข้อมูลเชิงความหมาย ว่าโปรแกรมทำอะไรได้ จึงควรตั้งให้ดี

  • ไม่เข้าใจว่าการใช้ dependency ภายนอกแล้วอวด จำนวนบรรทัดโค้ด แทนที่จะเป็นจำนวน \r\n ทั้งหมด มีความหมายอะไร
    ไม่มีหน่วย SI สำหรับวัด codebase ก็จริง แต่ผมคิดว่าภาระทางความเข้าใจควรถูกวัด somehow

    • ไม่ใช่มาตรฐานทางการ แต่ทีมเราบางครั้งอ้างอิง https://grugbrain.dev แล้วพูดว่า “โค้ดนี้ไม่ค่อย grug” หรือ “โค้ดนี้ค่อนข้าง grug”
    • เสิร์ชเอนจิน 80 บรรทัดตัวมันเองไม่ได้ใช้ dependency ภายนอก นำเข้าแค่ collections, math, string และทั้งหมดเป็น standard library
      แต่ถ้าพูดให้แม่นยำกว่า อาจควรเรียกว่า “search engine engine” crawler กับ interface ไม่ได้รวมอยู่ใน 80 บรรทัดนั้น แต่จำเป็นต้องมีในรูปแบบใดรูปแบบหนึ่ง และ implementation ที่นำเสนอเพิ่มทั้งจำนวนบรรทัดและไลบรารีขึ้นพอสมควร ถึงอย่างนั้นไลบรารีเหล่านั้นก็ไม่ได้เกี่ยวกับตัวเสิร์ชเอนจินเอง ถ้าเริ่มนับ dependency ทั่วไปอย่าง pandas หรือ fastapi ก็อาจต้องนับโค้ดหลายล้านบรรทัดของระบบปฏิบัติการ เฟิร์มแวร์การ์ดเครือข่าย และความซับซ้อนของฮาร์ดแวร์ด้วย
    • มีเหตุผลอะไรที่ไม่ควรฉลอง ความสำเร็จของอุตสาหกรรมที่ทำให้ของแบบนี้สร้างได้ใน 80 บรรทัด ไหม?
    • ในที่นี้มีความหมาย ถ้าเป็น “เสิร์ชเอนจินที่ทำด้วย Python 4000 บรรทัด” คนส่วนใหญ่ก็คงเลื่อนผ่าน แต่ 80 บรรทัด สั้นพอที่จะลองเปิดดูสักครั้ง
    • วิธีแบบเก่ามี cyclomatic complexity

  • ชอบนะ เอนจินแนะนำ ที่มีไม่ถึง 20 บรรทัดและใช้ร่วมกับเสิร์ชเอนจินก็เป็นไปได้ ถ้าเก็บ session log ของ URL ที่คลิกไว้ ก็สามารถดู sliding window หลัง URL ปัจจุบันในแต่ละ session แล้วให้น้ำหนักสูงขึ้นกับลิงก์ที่อยู่ใกล้กว่า เพื่อสร้างรายการแนะนำได้
    เมื่อจัดเรียงผลลัพธ์แนะนำแล้วเหลือไว้แค่ N อันดับแรก ก็จะได้รายการ URL แนะนำสำหรับ URL หนึ่ง ๆ ถ้าปรับแต่งอีกเล็กน้อย ก็สามารถผสมคำค้นหาที่ป้อนกับ URL ที่คลิกลงใน log แล้วดึง คำแนะนำการสะกด ออกมาได้

  • ยอดเยี่ยมและให้ความรู้มาก แต่ขออย่านำไปใช้จริงในโปรดักชัน :-)
    เมื่อก่อนผมเคยต้องการของคล้าย ๆ กัน แต่ขนาดใหญ่กว่านิดหน่อย มีเอกสารระดับหลายหมื่นฉบับ และคำตอบก็เป็นอย่างที่มักเป็นเสมอคือ sqlite โครงสร้างก็เหมือนกับที่อยู่ตรงนี้ แต่เป็นรูปแบบที่มีคนอื่นเขียน ชั้นการทำ persistent inverted index ให้แทนแล้ว

    • SQLite FTS ผมใช้แทบทุกที่ และไม่เคยทำให้ผิดหวังเลย
    • จริง ๆ แล้วมีสูตรเดียวกันอยู่ด้วย คอมเมนต์นี้ทำให้รู้สึกเหมือน “ขนลุกเพราะเข้าใจขึ้นมาทันที” เลย

  • ถ้าค้นหาใน Google ด้วยเครื่องหมายคำพูดคู่แบบ "search engine" ก็จะแสดงเฉพาะผลลัพธ์ที่มีสองคำนั้นปรากฏตามลำดับนั้น
    อย่างน้อยในบางกรณีก็เป็นแบบนั้น แต่น่าเสียดายที่ไม่ใช่เสมอไป สิ่งที่ผู้ใช้ขั้นสูงต้องการคือ “grep สำหรับเว็บ” ไม่ใช่ “สิ่งที่ Google อยากบอกให้เห็น”

    • ผมกล้ารับประกันว่าแทบไม่มีใครต้องการ “grep สำหรับเว็บ” จริง ๆ หรอก แม้เทียบกับเสิร์ชเอนจินที่ทำ query expansion เพียงเล็กน้อยมาก ๆ grep สำหรับเว็บก็แย่กว่าอย่างชัดเจน
      จริงอยู่ว่า Google ใช้อิสระมากเกินไปตอนตีความ query แต่ก็มีการประมวลผลหลายอย่างที่เสิร์ชเอนจินใด ๆ ทำแล้วย่อมดีกว่าไม่ทำแน่นอน ปัญหาของ Google Search ตอนนี้คือยากที่จะอนุมานว่าทำไมผลลัพธ์แบบนั้นถึงออกมา และดูเหมือนว่าเป็นเพราะพึ่งพา embedding มากเกินไปในการเปรียบเทียบสตริง น่าหงุดหงิดเวลาที่ "cat food" ไป match กับ "dog restaurant" แบบที่ใน embedding space อาจใกล้กันเชิงความหมาย แต่ไม่สอดคล้องกับการอนุมานของมนุษย์

  • ผมว่าไม่ค่อยแฟร์ที่จะบอกว่าเป็น โค้ด 80 บรรทัด ทั้งที่ใช้ไลบรารีภายนอกอย่าง feedparser, bs4 ฯลฯ

    • ถ้าสร้างบน elasticsearch ผมก็คงเห็นด้วย แต่ถ้า ส่วนที่เป็นเสิร์ชเอนจินจริง ๆ ถูก implement อยู่ใน 80 บรรทัดนั้น ผมว่าก็แฟร์แล้ว ไลบรารีที่นำมาใช้เป็นประเภทที่ไม่ควรต้อง implement เองอยู่แล้ว
      บางครั้งบทความแนว “สร้างเสิร์ชเอนจินของตัวเอง” จริง ๆ แล้วเป็นคู่มือติดตั้ง searxng หรือ yacy แต่กรณีนี้ไม่ใช่แบบนั้น
    • ถ้า dependency นั้นเป็นของที่ใช้กันทั่วไปมากและเป็นกระแสหลัก ผมว่าก็โอเค

  • ดีเลย การเพิ่มฟีเจอร์ fuzzy search เข้าไปตรงนี้ก็น่าจะไม่ยากนัก เช่น ให้การค้นหา "hackrnew" match กับ "hackernews" โดยหาผลลัพธ์ที่ระยะ prefix edit distance ต่ำกว่าหรือเท่ากับค่า threshold หนึ่ง
    แนวคิดพื้นฐานคือเพิ่ม inverted index อีกหนึ่งตัว โดยใช้ n-gram (ปกติคือ 3-gram) ของคำในคอลเลกชันเอกสารเป็น key และให้ posting เป็นคำหรือ ID ของคำที่มี n-gram นั้นปรากฏอยู่ สามารถใช้ lemma ที่ว่า ถ้า PED(x, y) <= delta แล้ว |N(x) ∩ N(y)| >= |N(x)| - n ∙ delta ได้ คำนวณ n-gram ของอินพุต x แล้วดึง posting ของแต่ละ n-gram ออกมา จากนั้นรวมรายการซ้ำ ก็จะได้จำนวน n-gram ที่แชร์กับคำผู้สมัครแต่ละคำ y ถ้าจำนวนนี้มากกว่าเกณฑ์จึงค่อยคำนวณ PED จริง และถ้าน้อยกว่านั้นก็ข้ามไป ช่วยลดการคำนวณราคาแพงได้มาก
    จากนั้นก็นำรายการคำที่ได้ไป query กับ index เดิมได้เลย เมื่อก่อนผมใช้แนวทางนี้ตอนทำเสิร์ชเอนจิน fuzzy search ฝั่ง client ด้วย JS ที่ https://dont.watch/ ถ้าดูในโค้ด JS จะเห็นว่ามีการส่ง inverted index และ n-gram index ที่บีบอัดแล้วเป็นไฟล์ JS ไปตรง ๆ ตัวเสิร์ชเอนจินจริง ๆ เป็น JS ประมาณ 300 บรรทัดโดยไม่มี dependency ภายนอก และมีแค่ heuristic พื้นฐานมาก ๆ สำหรับปรับปรุงผลการค้นหา

    • ถ้าใช้วิธีนั้น ขนาด index จะเพิ่มขึ้นเท่าไร?