概念地圖・後綴樹
作者 山姆（謝冠生）・喵喵書評創辦人
發布
分類：系統
這一頁不只是把一個概念解釋一遍——一張自己畫的結構圖，加上拿台灣情境從頭走一次的實例演練、這個框架什麼時候會騙你，以及它接回 P.A.I.N. 之後長什麼樣。一頁必須交付的三層 →
後綴樹：把一份文本索引成一棵樹，任何片語一次問到底
三十七通催收電話轉成文字之後，主管想知道同一句話到底被講了幾次。後綴樹是替這種問題準備的一棵樹：它把一個字串的所有後綴，全部收進同一棵樹裡，每一條邊上掛的是一整段子字串。建好之後，問「這串字出現過嗎、出現在哪幾個位置」的成本，只跟你問的那串字有多長有關——原文一萬字還是一百萬字，查起來差不多。代價也很直接：建樹那一次要把整份文本掃過，還要準備原文數倍到十幾倍的記憶體。會盯著它看的人，手上通常有一份會被反覆盤問的文本——一批客服通話的文字紀錄、一疊制式合約、一整年的機台日誌。
邊上那串字，葉子上那個號碼
先把圖上的六個部位認一遍，後面的判準才有東西可以套。
| 圖上的元素 | 在 banana$ 這棵樹上是什麼 | 它換來的能力 |
|---|---|---|
| 根到葉的一條路徑 | 沿路把邊上的字接起來，就得到一個後綴 | 七條路徑對上七個後綴，一個不漏 |
| 邊上的標籤 | 一整段子字串，例如 na$ 這三個字元共用一條邊 | 節點數被壓住，樹才存得下 |
| 內部節點（實心圓，3 個） | 至少兩個後綴走到這裡開始分岔 | 每一個都標記著一串重複出現過的字 |
| 葉子（方框，7 片） | 框裡的號碼是那個後綴在原字串的起始位置 | 查到之後直接知道它落在第幾個字元 |
| 節點底下掛著幾片葉子 | 走到那個節點的那串字，在原文就出現幾次 | a 底下三片、ana 底下兩片、na 底下兩片 |
| 結束符 $ | 讓每一個後綴都有專屬於自己的收尾 | 少了它，a 與 na 這兩個後綴會停在內部節點上，長不出葉子 |
這張表裡最值錢的是倒數第二列。找重複片語這件事，在後綴樹上退化成一個機械動作——走過每一個內部節點，數它底下掛了幾片葉子，就知道那串字被講過幾次。banana$ 這種七個字元的玩具字串看不出威力；把它換成十二萬字元，威力就是全部的差別。字典樹一條邊只放一個字元，節點數跟著字元數走。後綴樹一條邊放一整段子字串，只有真的分岔的地方才長節點——這就是圖上那個「壓縮」的意思。
什麼題目值得付這筆記憶體
一、這份文本會被問幾次。一家做債權委外的公司，每個月有一批新進案件的通話要聽。如果每一批聽完就結案、之後再也不回頭翻，那建樹那一次的掃描成本就白付了——直接用字串比對從頭掃過去，反而更快收工。真正划算的場景是另一種：同一批通話，法遵要查一次、主管教育訓練要查一次、客訴來了再查一次。自問：同一份文本會被查很多次嗎？
二、你要查的東西有沒有邊界。催收的稽核關鍵字常常長成半句話，而且卡在詞的中間——「再不還就」、「跟你公司講」。這種片語事先切不乾淨，字典切詞器一刀下去就把它切散了。後綴樹不管詞的邊界，它認的是連續的字元序列，你問幾個字它就對幾個字。要查的東西如果本來就是規規矩矩的完整詞，倒排索引更省。自問：要查的是任意子字串，還是事先切好的詞？
三、文本從哪一頭長出來。往結尾接字元其實可以線上加——Ukkonen 的演算法本來就是邊讀邊建，今天的通話補進去不必重來。麻煩的是另外兩種長法：多加一份新的案件檔案、或者從開頭裁掉過期的資料，這兩種多半得重建，或者改用廣義後綴樹。債權催收的資料偏偏兩種都會遇到，排程重建的時窗要先算進去。自問：文本會不會一直長？
四、記憶體那張帳單誰簽。這是最常被跳過的一項。十二萬字元的通話文字，本體只有幾百 KB，聽起來毫無壓力；建成後綴樹之後，實際佔用會是原文的數倍到十幾倍，依實作而定。一台跑著營運系統的機器，多這一塊常駐記憶體就得重新排預算。把它擠在跟資料庫同一台機器上，通常是第一個炸掉的地方。自問：記憶體預算容不容得下原文的數倍到十幾倍？
三十七通電話的文字，找一次重複
底下這家台灣中部的債權催收委外公司，是為了把這個結構講清楚而編出來的示意情境，沒有指涉任何真實公司。主管想知道的只有一件事：同一句話，到底被講了幾次。
- 先把電話變成字：37 通催收通話轉成文字，合計約 12.4 萬字元。三十七段接成一條長字串，每一段之間插一個絕不會出現在內文的分隔符。分隔符這一步省不得，它擋住跨通話拼出來的假重複
- 建一棵樹：整份掃過一遍，長出一棵後綴樹。這一次掃描是全部的前期成本，後面所有的查詢都吃它的老本。之後每問一句，成本只跟那句話有多長有關
- 設一個門檻：只要「出現 5 次以上、長度 8 字以上」的片語。走過每一個內部節點，數底下的葉子，符合門檻的收進來——找出 23 串。門檻是人訂的，樹只負責把數字端上來
- 看榜首那一串：最常出現的那一串出現了 31 次。37 通裡有 31 通，開場用的是同一句話。三十七個人的開場白，其實是一份沒人承認的口頭腳本
- 算一下對照組：不建樹的話，兩兩比對要 37×36÷2＝666 組，每一組還要再逐句掃一次。666 這個數字，就是這件事以前一直沒人動手的原因
那 23 串裡，真正讓主管坐直的只有榜首那一句。31 通用同一句開場，代表訓練教材其實已經生效了——只是生效的方式，是把三十七個人的第一句話壓成同一句。接下來的問題就從技術跳到管理：這句開場的回收率好不好？如果好，剩下那 6 通該補訓；如果不好，那就是整批人被同一句話拖著往下走。後綴樹只做到「把 31 這個數字端上桌」，它不知道這 31 次裡有幾次讓對方掛電話。從這裡開始，樹幫不上忙了——要往下走，得把通話結果併回來一起看。以上為說明結構用的示意情境，僅供理解框架之用。
這棵索引什麼時候會騙你
- 線性時間是理論結果，常數很大。教科書寫「線性時間建樹」的時候，藏在那個線性後面的常數項相當可觀——節點配置、指標跳轉、快取失效，每一項都在收錢。文本短的時候，一個沒有任何理論光環的暴力比對，實測上常常更快收工。門檻在哪裡沒有標準答案，要拿你自己那份資料實際跑一次。別因為某個結構「複雜度比較漂亮」就先寫它。
- 兩句話講同一件事，樹上會落成兩片葉子。「我這個月真的沒辦法」與「這個月周轉不過來」，在後綴樹上是兩串毫不相干的字元序列，分別掛在相隔很遠的兩片葉子底下，誰也看不見誰。它抓的是字面上的重複。真正的語意群聚要靠別的工具——這一點在客服、催收、客訴這類「同一個意思有一百種講法」的文本上，會直接決定你找到的 23 串有多少價值。
- 記憶體開銷最常被低估，而且它只是索引。同樣的需求換成後綴陣列（suffix array），空間省得下來，代價是實作起來比較拐彎、二分搜的邊界條件很容易寫錯。更要緊的是定位：後綴樹做的是子字串索引這一件事。斷詞、同義詞擴展、相關性排序、分頁，這些東西它一項都沒有——把它當搜尋引擎推上線，會在使用者第一次問「哪一筆最相關」的時候卡住。
痛點視角：壓掉的節點去了哪裡
這棵樹把成本全押在建好之前。
被壓掉的那些節點，換回來的是往後每一次查詢的時間——付款在前，收款在後，而且收多少要看你之後真的問了幾次。這件事的形狀，跟《痛點》裡反覆講的那個判斷很像：你花的力氣，得有人願意回頭用第二次，它才算數。做一份索引、寫一套後台、建一張報表，都是同一種賭注。這張圖畫得出哪一串字被重複了三十一次，畫不出那三十一通電話裡有沒有一個人真的想還錢。P.A.I.N. 的第一個字母問的是誰在痛——後綴樹回答不了這一題，它只能把「同一句話講了 31 次」這個事實推到你面前，剩下的判斷還是人的。真正危險的用法是倒過來：先建好一套很聰明的索引，再回頭找它能解的問題。今晚可以做的事很小——翻一下你手上那份「已經整理好卻沒人再看第二眼」的資料，算算它這半年被打開過幾次。
讀者最常卡住的三個地方
後綴樹跟字典樹（trie）到底差在哪？
差在一條邊上放什麼。字典樹一條邊只放一個字元，走 banana$ 這七個字元就要走七條邊，節點數跟著字元數線性長。後綴樹一條邊放一整段子字串——圖上那條標著 banana$ 的邊，一條就吃掉七個字元；只有真的出現分岔的位置才配一個節點。所以同一份資料，後綴樹的節點數被壓到跟後綴數同一個量級，這也是它為什麼叫「壓縮」字典樹。壓縮改變的是儲存量，查詢邏輯本身沒變：一樣是從根往下走，比對邊上的字。
建一棵後綴樹要吃掉多少記憶體？
沒有一個可以背起來的數字，實務上落在原字串的數倍到十幾倍，依實作而定。差別來自你怎麼存：每個節點要記幾個子節點、子節點用陣列還是雜湊表還是平衡樹、邊上的字串是複製一份還是存成一對起訖索引。所以正確的做法是拿你自己那份資料建一次，量出真實佔用，再去談要放在哪台機器上。先拿理論公式算一個數字、然後照那個數字編預算，是最容易在上線當天出事的做法。真的裝不下，先考慮後綴陣列。
文本一直在長，是不是每次都要整棵重建？
要看它從哪一頭長。往結尾接字元可以線上處理，Ukkonen 的演算法本身就是邊讀邊建的，新進來的字元接著加就好。麻煩的是另外兩種：從開頭刪掉過期資料，或者多加一整份獨立的新文件。前者破壞了已經建好的路徑，後者需要的是廣義後綴樹（generalized suffix tree），也就是把多份文件一起建進同一棵樹、葉子上同時記文件編號與位置。如果你的資料是「每天新增一批、保留半年」，多半還是排一個定期重建的批次比較省心。
壓掉的節點換回來的是時間，付出去的是記憶體——這筆帳該不該付，得看那份文本之後會被翻幾次。想比較另外兩種索引的取捨，可以順路看看倒排索引的詞與文件編號，那張圖要求你先把詞切好；而TF-IDF 的詞語權重秤的是哪一個詞重要，這裡找的是哪一串字反覆出現。
喜歡這篇文章嗎？
每週幫你拆二本好書，把判斷力、好書金句、好問題，直送你的信箱。
不適合你可隨時退訂 · 每週兩封，陪你把書讀進生活。
送出即表示同意我們依隱私權政策使用你的 email。