close
Posted By Mr. Thursday
在〈二元樹在排序的應用〉裡面，我們提到了演算法就是完成一件事情的步驟，資料結構則是和演算法搭配，讓步驟有運作的東西，像是刮鬍刀的步驟，會運作在刮鬍刀或是插頭上面。「樹」(tree) 是一種資料結構，有樹根樹枝，看起來像是倒立的一棵樹。二元數則是每個節點只有兩個分支的樹。此外，我們可以用二元樹這個資料結構，完成「排序」(sorting) 的演算法。下面是一段各種排序演算法的影片：
除了排序以外，今天要和各位介紹，當我們把資料用一棵樹排序之後，要如何進行搜尋？排序或是沒有排序，對搜尋的效率有甚麼樣子的影響？我們先看看下面這兩張圖，左邊是排序過程，右邊是搜尋過程的動畫：
我們可以看到，不管是搜尋過程，還是排序過程，在二元樹上面的步驟都差不多：先比較現在的節點，如果比較小，就往左邊走，比較大，就往右邊走，一直到達樹的底部為止。
因此，現在的差別就在於，有排序過的樹，跟一棵沒有排序過的樹，搜尋的效率有哪些差別？一棵沒有排序過的樹，如果我們要在裡面找是否有某個數字，最差的情況下我們必須把整棵樹都走完，才會找到我們要的數字，或是回報沒有這個數字。然而如果我們用了二元樹在輸入每一個新的數字的時候，就按照剛才的演算法排序過，那麼這棵二元樹永遠都會維持的一個關係，就是對每一個節點來說，左邊的節點一定比他小，右邊的節點一定比他大。也因此我們如果要在這一棵樹裡面，尋找是否有某個數字的時候，我們比較目前的節點和我們要找的數字，如果比較小就往左邊，比較大就往右邊走。這樣子保證我們不會漏找，卻同時減少我們需要拜訪的節點。
如果我們在認真去分析的話，我們可以發現，我們最差的情況，最多找和樹高 (tree height)一樣多節點就可以了，也就是說如果這棵樹的高 (像是上面那一張動畫裡面的樹) 如果只有三個節點的高度，那麼我們最多只要尋找三次就能找到。然而同樣的一棵樹，沒有經過排序，我們最多需要尋找7棵節點。如果再用數學表示的話，一個有n個節點的二元樹，樹高就是 log_2(n) 了！
因此我們可以發現，排序演算法的用處在哪邊了！一堆病歷，或是一堆電話號碼，如果沒有排序過，我們要從裡面找出所要的病歷，所要的電話號碼，最多要把全部的病歷都找一遍。如果我們用二元樹和搭配的演算法，把病歷和電話號碼先排序過，那麼我們尋找病歷或電話號碼的時候，可以節省指數倍的時間！原來最多找7次，排序過後只要找3次！
搜尋某方面，也就像是人類的記憶。行為認知上來說，記憶有兩種情況：(1) 看到同一個東西的時候，能夠回想起我看過。(2) 看到某見東西的重要部份 (key)，可以回想起整件事情。上面提到的二元樹搜尋演算法，可以算是第一種情況，如果數字是代表病歷號碼，找到某個節點後，會有一個連結到病歷內容，那麼上面的二元樹搜尋演算法，就是第二種情況，也就是以 key 找資料的情況。
在這邊還要再提的部分，是以 key 找資料的情況。有時候我們稱這個 key 在電腦裡面是一個地址 (adress) ，因此這種尋找方式，可以稱為 adress-based memory，根據東西的地址來找資料，譬如說病歷號碼，可以當程式病歷的地址 (address)，我們搜尋病歷，就先搜尋病歷號碼，然後提取該號碼代表的病歷內容。搜尋引擎來說，就是把關鍵字keyword當成地址，每個地址連結到某個網頁。
另外一種搜尋方式，就是用內容為 key的情況，這時候我們稱之為 content-based memory。這種記憶就類似「以文找文」的方式，或是「以圖找圖」的方式，沒有索引，直接用內容來提取我們想要找的內容。人類的記憶我想滿多部分都是 content-based memory，也就是我們大腦神經網絡，會把資料用一種特別方式儲存起來，當我們在頭腦裡面尋找資料的時候，我們是用內容來尋找比較多，比較少像是書本索引一般，用關鍵字當地紙來找我們想要找的東西。類神經網路 (artificial neural network) 大部分也都是用 content-based memory比較多。
然而比較困難的地方，我想是在於部分內容當作key的情況，也就是我們以文找文，但是只有一部分的文章內容，要找出原來完整的文章，卻又沒有索引地址。譬如說我們記得某張照片裡面有一座山、一條河流、和一棟房屋，但是我們也沒有再資料庫裡面對每張照片開一個欄位，紀錄每張照片是否有出現山、河流、或房屋，這個時候就是 content-based memory的情況，而且提取的key只有原來內容的部分，想要找尋完整的一張照片。使用機率為基礎的演算法，或是從生物角度研究大腦記憶的方法，都是想要解決這個問題。
在困難一點，我們可能還有前後文、或稱為情境的問題 (context) 。找圖片的時候，我們可能說照片裡面有一做山，但是文字一般性的敘述，有時候又會讓每個人心中想像的山有所出入，你想的可能是長滿樹木的山，我想的可能是積雪覆蓋的山。又另外一種情況是，我們可能用一張蘋果的照片，來找相似的圖片，但是我們是在「水果」的前後文情境裡面，就不能找到 Apple 產品的圖片了。因此這些問題的難度又加一層了。下回在介紹用樹來表示一個本體論 (Ontology) 的時候，再和各位詳細探討一下！
line
在〈二元樹在排序的應用〉裡面，我們提到了演算法就是完成一件事情的步驟，資料結構則是和演算法搭配，讓步驟有運作的東西，像是刮鬍刀的步驟，會運作在刮鬍刀或是插頭上面。「樹」(tree) 是一種資料結構，有樹根樹枝，看起來像是倒立的一棵樹。二元數則是每個節點只有兩個分支的樹。此外，我們可以用二元樹這個資料結構，完成「排序」(sorting) 的演算法。下面是一段各種排序演算法的影片：
[youtube=http://www.youtube.com/watch?v=JdXoUgYQebM]
除了排序以外，今天要和各位介紹，當我們把資料用一棵樹排序之後，要如何進行搜尋？排序或是沒有排序，對搜尋的效率有甚麼樣子的影響？我們先看看下面這兩張圖，左邊是排序過程，右邊是搜尋過程的動畫：
我們可以看到，不管是搜尋過程，還是排序過程，在二元樹上面的步驟都差不多：先比較現在的節點，如果比較小，就往左邊走，比較大，就往右邊走，一直到達樹的底部為止。
因此，現在的差別就在於，有排序過的樹，跟一棵沒有排序過的樹，搜尋的效率有哪些差別？一棵沒有排序過的樹，如果我們要在裡面找是否有某個數字，最差的情況下我們必須把整棵樹都走完，才會找到我們要的數字，或是回報沒有這個數字。然而如果我們用了二元樹在輸入每一個新的數字的時候，就按照剛才的演算法排序過，那麼這棵二元樹永遠都會維持的一個關係，就是對每一個節點來說，左邊的節點一定比他小，右邊的節點一定比他大。也因此我們如果要在這一棵樹裡面，尋找是否有某個數字的時候，我們比較目前的節點和我們要找的數字，如果比較小就往左邊，比較大就往右邊走。這樣子保證我們不會漏找，卻同時減少我們需要拜訪的節點。
如果我們在認真去分析的話，我們可以發現，我們最差的情況，最多找和樹高 (tree height)一樣多節點就可以了，也就是說如果這棵樹的高 (像是上面那一張動畫裡面的樹) 如果只有三個節點的高度，那麼我們最多只要尋找三次就能找到。然而同樣的一棵樹，沒有經過排序，我們最多需要尋找7棵節點。如果再用數學表示的話，一個有n個節點的二元樹，樹高就是 log_2(n) 了！
排序、搜尋、與記憶
因此我們可以發現，排序演算法的用處在哪邊了！一堆病歷，或是一堆電話號碼，如果沒有排序過，我們要從裡面找出所要的病歷，所要的電話號碼，最多要把全部的病歷都找一遍。如果我們用二元樹和搭配的演算法，把病歷和電話號碼先排序過，那麼我們尋找病歷或電話號碼的時候，可以節省指數倍的時間！原來最多找7次，排序過後只要找3次！
搜尋某方面，也就像是人類的記憶。行為認知上來說，記憶有兩種情況：(1) 看到同一個東西的時候，能夠回想起我看過。(2) 看到某見東西的重要部份 (key)，可以回想起整件事情。上面提到的二元樹搜尋演算法，可以算是第一種情況，如果數字是代表病歷號碼，找到某個節點後，會有一個連結到病歷內容，那麼上面的二元樹搜尋演算法，就是第二種情況，也就是以 key 找資料的情況。
在這邊還要再提的部分，是以 key 找資料的情況。有時候我們稱這個 key 在電腦裡面是一個地址 (adress) ，因此這種尋找方式，可以稱為 adress-based memory，根據東西的地址來找資料，譬如說病歷號碼，可以當程式病歷的地址 (address)，我們搜尋病歷，就先搜尋病歷號碼，然後提取該號碼代表的病歷內容。搜尋引擎來說，就是把關鍵字keyword當成地址，每個地址連結到某個網頁。
另外一種搜尋方式，就是用內容為 key的情況，這時候我們稱之為 content-based memory。這種記憶就類似「以文找文」的方式，或是「以圖找圖」的方式，沒有索引，直接用內容來提取我們想要找的內容。人類的記憶我想滿多部分都是 content-based memory，也就是我們大腦神經網絡，會把資料用一種特別方式儲存起來，當我們在頭腦裡面尋找資料的時候，我們是用內容來尋找比較多，比較少像是書本索引一般，用關鍵字當地紙來找我們想要找的東西。類神經網路 (artificial neural network) 大部分也都是用 content-based memory比較多。
然而比較困難的地方，我想是在於部分內容當作key的情況，也就是我們以文找文，但是只有一部分的文章內容，要找出原來完整的文章，卻又沒有索引地址。譬如說我們記得某張照片裡面有一座山、一條河流、和一棟房屋，但是我們也沒有再資料庫裡面對每張照片開一個欄位，紀錄每張照片是否有出現山、河流、或房屋，這個時候就是 content-based memory的情況，而且提取的key只有原來內容的部分，想要找尋完整的一張照片。使用機率為基礎的演算法，或是從生物角度研究大腦記憶的方法，都是想要解決這個問題。
在困難一點，我們可能還有前後文、或稱為情境的問題 (context) 。找圖片的時候，我們可能說照片裡面有一做山，但是文字一般性的敘述，有時候又會讓每個人心中想像的山有所出入，你想的可能是長滿樹木的山，我想的可能是積雪覆蓋的山。又另外一種情況是，我們可能用一張蘋果的照片，來找相似的圖片，但是我們是在「水果」的前後文情境裡面，就不能找到 Apple 產品的圖片了。因此這些問題的難度又加一層了。下回在介紹用樹來表示一個本體論 (Ontology) 的時候，再和各位詳細探討一下！
line
全站熱搜
留言列表
