推 scwg:我 (ledia 應該也是) 自動採用 2. 的解釋, 因為 inverse 03/09 03:21 → scwg:list 可以 offline 建好, 之後這個演算法可以重複多次 03/09 03:22 我的想法和 scwg 一樣， 因為原本的題目其實沒有說明的很清楚，以下是我自己腦補的部份： 這個演算法想要做什麼？有一個猜測是，我覺得他的功能很像是搜尋時的預覽功能， 比如說我們用 google search "harry potter spell" 這三個關鍵字， 我所找到的第一筆結果長這樣： Harry Potter Spell List www.pojo.com/harrypotter/spelist.shtml - Cached Harry Potter Spell List. Here I think I got all the spells, charms, enchantments, curses, jinxes and all the other incantations. If there's any missing, e-mail us on the ... 另一個比較後面的結果長這樣： HPL: Encyclopedia of Spells - The Harry Potter Lexicon www.hp-lexicon.org/magic/spells/spells.html - Cached Dec 27, 2000 –Descriptions of spells and various magical effects in the Harry Potter universe. 第一行是網頁的 title, 第二行是網址，第三行開始則是內文的預覽， 那要如何產生一個好的預覽呢？ 我想這一題的目標：「找出一個最小的 window 來包含所有的關鍵字」可能就是一種方法 如果我們每次都是用原本的文件來產生這個 window 的話， （也就是 occurrence lists 要自己產生） 那這題至少是 O(|document size| * O(check word)) O(check word) 指的是檢查每個字到底是哪一個關鍵字所要花的時間 document size 以 word 為單位 突破這個限制的一種方法就是對文件做一些預處理，(所做的事和 indexing 應該差不多) 我們先對文件中的字產生他們的 occurrence list ， 這樣的花費也是 O(|document size| * O(check word)) (假設我們有辦法儲存這些資訊，以供日後使用) 然後，未來有人來搜尋時，我們可以根據事先做好的 occurrence list 來求解 在這種情況下，至少不用再花時間做 check word 。 以長遠的角度來看，或許可以省下不少時間。 另一方面，也因為在有 occurrence list 的狀況下， 我們已經可以做到 O(|document size|) 了， 所以我會想要試試看能不能做到 O(n) (n = key words 出現的總次數)。 而 Leon 在上一篇中所提到的 show_list 我們其實是沒有的， 因為我們在事前不知道使用者會搜尋哪一些字， 我們只能存每個字各自的 occurrence list ， 沒辦法產生 show_list 。 如果要把 occurrence list 合並成 show_list ， 這應該是沒辦法在 O(n) 的時間內做到，不然 merge sort 就會是 O(n) 了。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 36.226.38.104