<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    內(nèi)蒙古java團(tuán)隊(duì)

    j2se,j2ee開(kāi)發(fā)組
    posts - 139, comments - 212, trackbacks - 0, articles - 65
      BlogJava :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

    標(biāo)簽

    排序?鏈樹(shù)?GIS?POI?關(guān)鍵字?搜索算法

    概念闡述

    鏈樹(shù)及其相關(guān)概念

    本來(lái),數(shù)據(jù)結(jié)構(gòu)教科書(shū)中,不存在一種叫做“鏈樹(shù)”的數(shù)據(jù)結(jié)構(gòu),用Goolge也搜索不到。這種數(shù)據(jù)結(jié)構(gòu),是為了在GIS系統(tǒng)中進(jìn)行POI關(guān)鍵字高速搜索,在n叉樹(shù)的基礎(chǔ)上,改進(jìn)的一種數(shù)據(jù)結(jié)構(gòu),為了論述方便,姑且稱之為鏈樹(shù)。
    鏈樹(shù),就是在n叉樹(shù)的基礎(chǔ)上,給每個(gè)樹(shù)節(jié)點(diǎn)(包括樹(shù)根和葉子),都掛接上一個(gè)鏈表而形成的數(shù)據(jù)結(jié)構(gòu)。
    下圖就表示一棵典型的鏈樹(shù)

    圖1

    鏈樹(shù)的2個(gè)顯著特點(diǎn)是:
    ???1.?某樹(shù)節(jié)點(diǎn)所掛接的鏈表元素,為該樹(shù)節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)(如果有)所掛接的鏈表元素之集合(無(wú)重復(fù)節(jié)點(diǎn))。
    ???2.?鏈樹(shù)的根結(jié)點(diǎn),可以是一個(gè)虛擬節(jié)點(diǎn),代表系統(tǒng)中所有實(shí)體節(jié)點(diǎn)的祖先。這樣,就不必要形成鏈樹(shù)森林了。圖1的根結(jié)點(diǎn)就是一個(gè)虛擬節(jié)點(diǎn),其余節(jié)點(diǎn)都為實(shí)體節(jié)點(diǎn)。?

    排序鏈樹(shù)搜索算法

    該算法是指,根據(jù)關(guān)鍵字序列,從鏈樹(shù)根結(jié)點(diǎn)出發(fā),在鏈樹(shù)中路由,最終找到一個(gè)鏈樹(shù)路徑和關(guān)鍵字序列最大匹配的樹(shù)節(jié)點(diǎn),然后取其掛接鏈表的算法。
    以圖1所示之排序鏈樹(shù)為例,假定每個(gè)樹(shù)節(jié)點(diǎn)的關(guān)鍵字即為其上的標(biāo)簽字符,假如我們需要搜索的關(guān)鍵字序列為“ACI”,那么該算法的執(zhí)行順序?yàn)椋?br />1.從根結(jié)點(diǎn)出發(fā),查找關(guān)鍵字為‘A’的樹(shù)節(jié)點(diǎn)。
    根節(jié)點(diǎn)Root下有2個(gè)孩子,分別為‘A’和‘X’,因?yàn)榕判蜴湗?shù)節(jié)點(diǎn)的所有孩子都按一定規(guī)則排序,所以這一步可以使用二分查找來(lái)進(jìn)行,假定Root有n個(gè)孩子,那么這一步所花時(shí)間為lgn.
    2.在‘A’的所有孩子中查找關(guān)鍵字為‘C’的孩子。
    同樣用二分查找,假定‘A’有m個(gè)孩子,那么這一步所花時(shí)間為lgm。
    3.在‘C’的所有孩子中查找關(guān)鍵字為‘I’的孩子。
    同樣使用二分查找,假定‘C’有p個(gè)孩子,那么這一步所花時(shí)間為lgp
    綜上,關(guān)鍵字序列為“ACI”的搜索時(shí)間為lgn+lgm+lgp。
    根據(jù)鏈樹(shù)的特點(diǎn),有n>=k>=p,所以搜索長(zhǎng)度為3的關(guān)鍵字序列的時(shí)間復(fù)雜度為O(3lgn),推而廣之,我們得到更一般的排序鏈樹(shù)搜索算法復(fù)雜度:
    假如關(guān)鍵字序列長(zhǎng)度為k,系統(tǒng)中總的實(shí)體節(jié)點(diǎn)個(gè)數(shù)為n,那么在排序鏈樹(shù)搜索算法的時(shí)間復(fù)雜度為O(klgn)。

    關(guān)于POI

    在GIS系統(tǒng)中,對(duì)于地圖上的一個(gè)具有詳細(xì)信息的點(diǎn),我們稱之為POI(Point?Of?Interest)。比如名稱為“北京西單圖書(shū)大廈”的POI,就包含了該地點(diǎn)的一系列詳細(xì)信息,這些信息通常有:
    ???1.該P(yáng)OI的名稱,這里是“西單圖書(shū)大廈”
    ???2.該P(yáng)OI的經(jīng)緯度
    ???3.該P(yáng)OI的地址
    ???4.該P(yáng)OI的類型
    ???5.該P(yáng)OI的描述信息
    ???6.該P(yáng)OI的電話號(hào)碼
    ???7.該P(yáng)OI的網(wǎng)址
    ???8.該P(yáng)OI的照片
    ???9.該P(yáng)OI的音頻,視頻
    ???…...
    通常,一個(gè)城市中,就存在千百萬(wàn)個(gè)這樣的POI。其數(shù)據(jù)量是相當(dāng)?shù)木薮蟆?br />

    關(guān)于POI的關(guān)鍵字搜索

    在GIS相關(guān)應(yīng)用中,都會(huì)提供一種最基本的功能,就是根據(jù)用戶輸入的關(guān)鍵字,搜索到和該關(guān)鍵字相關(guān)的一系列POI,按照和用戶輸入字串匹配度由高到底的順序,把這些POI呈現(xiàn)給用戶。因?yàn)橛脩糨斎氲年P(guān)鍵字,可能和該P(yáng)OI的名稱相關(guān),也可能和該P(yáng)OI的地址,類型名稱,描述信息,網(wǎng)址等字段相關(guān)。理論上,只要POI的某個(gè)字段,或者某幾個(gè)字段的組合,和用戶輸入的關(guān)鍵字有關(guān)系,那么,這個(gè)POI就應(yīng)該出現(xiàn)在搜索結(jié)果列表的合適位置上。
    比如用戶輸入的關(guān)鍵字為“北大”,那么搜索出來(lái)的POI可能有:
    ??北大荒(名字中包含’北’,‘大’,且這2個(gè)字連在一起)
    ??北京大學(xué)(名字中包含’北’,‘大’,這2個(gè)關(guān)鍵字被隔開(kāi)了,稱之為跳字)
    ??北京郵電大學(xué)(名字中包含’北’,‘大’,跳字)
    ??大北窯(名字中包含‘北’,‘大’,但這2個(gè)關(guān)鍵字被顛倒了,稱之為逆字)
    ??未名湖(地址中含有‘北‘,‘大’二字)
    ??……
    當(dāng)然按照我們一般的思路,北京大學(xué)應(yīng)該排在第一位,因?yàn)橐话銇?lái)說(shuō),北大指的就是它。所以GIS系統(tǒng)要求在本次搜索中,北京大學(xué)應(yīng)該排在第一位。
    為了簡(jiǎn)化問(wèn)題,本文只限于對(duì)POI的名稱這一字段進(jìn)行關(guān)鍵字搜索。也就是說(shuō),只把名稱字段和用戶輸入字串有關(guān)聯(lián)的POI搜索出來(lái)。

    如何在POI關(guān)鍵字搜索中應(yīng)用鏈樹(shù)搜索算法

    如何在POI關(guān)鍵字搜索應(yīng)用鏈樹(shù)呢,我們舉例來(lái)說(shuō)。假定某城市中存在5個(gè)POI,其名稱分別是:
    ??北京大學(xué)
    ??北京郵電大學(xué)
    ??大北窯
    ??未名湖
    ??北大荒
    那么我們首先要做的工作就是建立排序鏈樹(shù),然后再依據(jù)排序鏈樹(shù),進(jìn)行關(guān)鍵字搜索。

    建立排序鏈樹(shù)

    建立排序鏈樹(shù)的工作分成以下幾步來(lái)做。
    ??1.分別給每個(gè)POI編號(hào),指定其ID,如下
    ???????北京大學(xué)(1)
    ???????北京郵電大學(xué)(2)
    ???????大北窯(3)
    ???????未名湖(4)
    ???????北大荒(5)
    每個(gè)POI的詳細(xì)信息,可以存在一個(gè)二進(jìn)制文件(raw?data)中,然后再建立一個(gè)索引文件,該文件包括5個(gè)索引條目,每個(gè)條目為一個(gè)POI在raw?data文件中的偏移量(offset)與長(zhǎng)度(size),該P(yáng)OI的索引條目序號(hào)(index),即為該P(yáng)OI的ID,這樣,根據(jù)該P(yáng)OI的ID,查詢索引文件,可以得到其在raw?data中的offset和size,進(jìn)而獲取其詳細(xì)信息。
    ??2.建立一個(gè)虛擬節(jié)點(diǎn)Root,作為排序鏈樹(shù)之根,把所有POI的ID鏈表掛接在Root上,這些ID按以空字符為關(guān)鍵字進(jìn)行POI查詢的呈現(xiàn)結(jié)果為序。

    圖2

    可以看到,如果以空字符進(jìn)行POI關(guān)鍵字查詢,輸出結(jié)果順序?yàn)?br />??????北大荒
    ??????北京大學(xué)
    ??????北京郵電大學(xué)
    ??????大北窯
    ??????未名湖
    很明顯,這是按拼音排序的。
    ??3.找出該城市所有POI名稱中涉及到的字符集合。
    在我們的例子中,這個(gè)集合包括為:{‘北’,‘大’,‘荒’,‘京’,‘學(xué)’,‘郵’,‘電’,‘窯’,‘未’,‘名’,‘湖’},共11個(gè)漢字。把該集合中的元素按字符的UNICODE編碼大小排序,我們姑且假定排序后的順序不變。
    ??4.把字符集合中的每一個(gè)字符都作為一個(gè)樹(shù)節(jié)點(diǎn)之關(guān)鍵字,并且讓該樹(shù)節(jié)點(diǎn)成為Root之子。如下圖

    圖3

    接下來(lái),我們要以每個(gè)孩子為根,建立一顆子鏈樹(shù),為了論述方便,本文只講述以‘北’字為樹(shù)根的這棵子鏈樹(shù),其他子鏈樹(shù),可以依此類推。
    ??5.對(duì)于圖3中每個(gè)子節(jié)點(diǎn),掛接上一個(gè)ID鏈表,這些ID所代表的POI的名稱中,都包含了該樹(shù)節(jié)點(diǎn)所對(duì)應(yīng)的字符。而且這些ID按照以該字符為關(guān)鍵字進(jìn)行POI查詢的呈現(xiàn)結(jié)果順序?yàn)樾颉@纭薄中纬傻逆湵砣缦?

    圖4

    之所以掛接鏈表是5,1,2,3,是因?yàn)槲覀冊(cè)谝浴薄诌M(jìn)行POI關(guān)鍵字查詢時(shí),GIS系統(tǒng)要求我們的輸出POI的列表順序必須是:北大荒,北京大學(xué),北京郵電大學(xué),大北窯這個(gè)順序。

    ??6.對(duì)于每一個(gè)根節(jié)點(diǎn),構(gòu)建其子節(jié)點(diǎn)列表。構(gòu)建規(guī)則為
    ???a.子節(jié)點(diǎn)所代表字符,能和其父節(jié)點(diǎn)所代表字符,出現(xiàn)在同一個(gè)POI的名稱中。
    ???b.子節(jié)點(diǎn)列表,按其所代表字符的UNICODE大小排序。
    比如‘北’字,其子節(jié)點(diǎn)列表為:

    圖5

    在這里,我們假定這幾個(gè)字的UNICODE排序結(jié)果如上圖所示。?
    大家可以看到,11個(gè)字符中,基本上所有字符都能和‘北’字組合,除了‘未’,‘名’,‘湖’這3個(gè)字符和‘北’字本身,當(dāng)然,如果有個(gè)POI叫“北北?”,那么‘北’字也會(huì)成為其本身的子節(jié)點(diǎn)。但是有一點(diǎn)是,父子節(jié)點(diǎn)的關(guān)鍵字可以相同,但是兄弟節(jié)點(diǎn)的關(guān)鍵字絕對(duì)不相同,他們是互斥的.
    ??7.結(jié)合父節(jié)點(diǎn)和每個(gè)子節(jié)點(diǎn),形成每個(gè)子節(jié)點(diǎn)所掛接的ID鏈表。構(gòu)建規(guī)則為:
    ??該ID鏈表所代表的POI列表,即為用戶以鏈樹(shù)路徑作為關(guān)鍵字,查詢出來(lái)的POI結(jié)果列表。
    比如對(duì)于根為‘北’字的鏈樹(shù),到這一步的結(jié)果為:

    圖6

    大家可以看到,對(duì)于路徑“北大”,所掛接的ID鏈表為1,5,2,3,也就是
    ????????北京大學(xué)
    ????????北大荒
    ????????北京郵電大學(xué)
    ????????大北窯
    這個(gè)順序,也就是GIS系統(tǒng)所要求的輸出順序。
    ??8.按照以上規(guī)律,繼續(xù)為第二層節(jié)點(diǎn)添加子節(jié)點(diǎn)。形成的高度為3的鏈樹(shù)如下圖所示

    圖7

    從上圖可以看到,顏色為紅色的鏈樹(shù)節(jié)點(diǎn)已經(jīng)到達(dá)葉子,無(wú)法再向下伸展了。?
    ??9.依此類推,還可以繼續(xù)向下擴(kuò)展鏈樹(shù)。最終的鏈樹(shù)深度為6,對(duì)應(yīng)著名稱最長(zhǎng)的POI節(jié)點(diǎn),也就是“北京郵電大學(xué)”,由于篇幅所限,就不再給出圖示了。
    至此,我們的排序鏈樹(shù)已經(jīng)建好了。關(guān)于鏈樹(shù)的建立,還有幾個(gè)地方要說(shuō)明一下:
    ????a.關(guān)于ID鏈表的排序
    ID鏈表的順序,需要我們的POI數(shù)據(jù)處理程序按照一定的規(guī)則來(lái)實(shí)現(xiàn),除了通用的一些規(guī)則外,還有些特定的簡(jiǎn)稱數(shù)據(jù)要處理,比如“北大”所對(duì)應(yīng)的POI列表,第一條通常應(yīng)該是“北京大學(xué)”,而不是“北大荒”。??
    ????b.關(guān)于排序鏈樹(shù)的存儲(chǔ)
    為了加快搜索速度,排序鏈樹(shù)森林中的冗余數(shù)據(jù)很多,所以實(shí)現(xiàn)者應(yīng)該認(rèn)真考慮文件存儲(chǔ)格式,以便節(jié)約存儲(chǔ)空間。?

    根據(jù)排序鏈樹(shù),按關(guān)鍵字搜索POI

    建立了排序鏈樹(shù)之后,我們就可以按排序鏈樹(shù)搜索算法,來(lái)進(jìn)行POI關(guān)鍵字查詢了。例如用戶如果輸入的關(guān)鍵字為“北大”2字,先從Root根節(jié)點(diǎn)出發(fā),根據(jù)關(guān)鍵字序列,逐級(jí)向下路由,得到查詢結(jié)果1,5,2,3。然后根據(jù)這些POI?ID,從raw?data文件中檢索出詳細(xì)信息即可。因?yàn)椴捎昧伺判蜴湗?shù)搜索算法,對(duì)于長(zhǎng)度為k的關(guān)鍵字,在POI總量為n的情況下,POI關(guān)鍵字查詢的時(shí)間復(fù)雜度為:
    ????????T?=?O(klgn)
    比一般的時(shí)間復(fù)雜度為O(kn)的GIS?POI關(guān)鍵字搜索算法,搜索速度有了較大的提升。

    算法優(yōu)劣分析

    綜上分析可知,采用排序鏈樹(shù)搜索算法進(jìn)行POI關(guān)鍵字查詢,其優(yōu)勢(shì)在于:
    ????*?搜索時(shí)間少,時(shí)間復(fù)雜度為O(klgn)
    ????*?可以讓用戶邊輸入,邊路由,邊搜索,實(shí)現(xiàn)實(shí)時(shí)搜索的功能,對(duì)于采用ajax效果的Web?GIS來(lái)說(shuō),猶為合適。
    ????*?此算法對(duì)通配符支持友好,比如用戶輸入的關(guān)鍵字串為“北大*”或者“北?荒”,此算法都能夠比較容易的適應(yīng)。
    其主要劣勢(shì)在于其ID鏈表的數(shù)據(jù)冗余度較大,而且建樹(shù)過(guò)程比較復(fù)雜,對(duì)POI數(shù)據(jù)處理程序的要求比較高。但是因?yàn)檫@些工作都在Server端完成,在目前多核,巨量?jī)?nèi)存,集群的server端硬件條件下,應(yīng)該都不是大問(wèn)題。

    作者信息

    Jagie,軟件開(kāi)發(fā)愛(ài)好者,可以通過(guò)chen_cwf@163.com與他聯(lián)系。本文來(lái)自于Jagie的google?page:http://chencwf.googlepages.com/linktree

    評(píng)論

    # re: 排序鏈樹(shù)搜索算法在GIS POI關(guān)鍵字搜索中的應(yīng)用  回復(fù)  更多評(píng)論   

    2010-10-29 14:44 by liuxuejin
    很好的文章!每個(gè)POI的詳細(xì)信息,可以存在一個(gè)二進(jìn)制文件(raw data)中,然后再建立一個(gè)索引文件,該文件包括5個(gè)索引條目,每個(gè)條目為一個(gè)POI在raw data文件中的偏移量(offset)與長(zhǎng)度(size),該P(yáng)OI的索引條目序號(hào)(index),即為該P(yáng)OI的ID,這樣,根據(jù)該P(yáng)OI的ID,查詢索引文件,可以得到其在raw data中的offset和size,進(jìn)而獲取其詳細(xì)信息。
    如果有一個(gè)類來(lái)實(shí)現(xiàn)(java)每一個(gè)POI,那么每一次都序列化?

    # re: 排序鏈樹(shù)搜索算法在GIS POI關(guān)鍵字搜索中的應(yīng)用  回復(fù)  更多評(píng)論   

    2011-06-01 00:10 by doctor
    這種樹(shù)狀的索引理論上雖然行,但是實(shí)際應(yīng)用完全不可能,占用的存儲(chǔ)空間巨大,無(wú)法想象。內(nèi)存只能駐留一小部分,檢索時(shí)內(nèi)存交換的時(shí)間就受不了,硬盤占用更不用說(shuō)。
    總結(jié):小兒科,沒(méi)經(jīng)驗(yàn)!

    # re: 排序鏈樹(shù)搜索算法在GIS POI關(guān)鍵字搜索中的應(yīng)用  回復(fù)  更多評(píng)論   

    2012-12-05 10:30 by chenzep
    沒(méi)有實(shí)用價(jià)值啊。
    假設(shè)一個(gè)POI的長(zhǎng)度為n,按照此方法生成的節(jié)點(diǎn)有f(n),則
    f(n)=f(n-1)+f(n-2)+...+f(0) + 1= 2^n
    以“北京大學(xué)”為例,則有2^4=16個(gè)節(jié)點(diǎn),分別如下:
    空字符串, 1個(gè)
    “北",”北京“,“北大”,“北學(xué)”,“北京大”,“北京學(xué)”,“北大學(xué)”,“北京大學(xué)” f(3)=8個(gè)
    "京" "京大" "京學(xué)” “京大學(xué)” f(2)=4個(gè)
    “大”,“大學(xué)” f(1)=2個(gè)
    "學(xué)“ f(0)=1個(gè)

    假設(shè)一個(gè)POI的長(zhǎng)度為8,則節(jié)點(diǎn)個(gè)數(shù)為2^8=256個(gè),一個(gè)省的POI數(shù)據(jù)為1M,
    則節(jié)點(diǎn)為256M,就算節(jié)點(diǎn)只是一個(gè)4字節(jié)的索引,所要空間也到達(dá)了1G,這是不現(xiàn)實(shí)的。

    # re: 排序鏈樹(shù)搜索算法在GIS POI關(guān)鍵字搜索中的應(yīng)用  回復(fù)  更多評(píng)論   

    2013-12-17 11:23 by 郭建山
    想法確實(shí)很好,使用起來(lái)沒(méi)法用呀!加入常用漢字3000,POI最長(zhǎng)8個(gè)字,那索引要建3000的8次方那么多嗎?
    主站蜘蛛池模板: 美女尿口扒开图片免费| 久久国产乱子伦精品免费午夜 | 亚洲啪AV永久无码精品放毛片| 亚洲av永久中文无码精品综合| 亚洲成熟丰满熟妇高潮XXXXX| 免费看国产成年无码AV片| 亚洲中文字幕无码久久2017| 产传媒61国产免费| 国产L精品国产亚洲区久久| 亚洲免费福利视频| 91精品国产免费久久久久久青草| 亚洲国产夜色在线观看| 国产免费不卡v片在线观看| 亚洲色最新高清av网站| 日本免费一区二区三区最新| 亚洲激情视频在线观看| 1024免费福利永久观看网站| 亚洲乱码在线观看| 99在线观看视频免费| 亚洲精品国产va在线观看蜜芽| 午夜不卡AV免费| 亚洲精品无码永久在线观看你懂的| 国内精品久久久久影院免费| 亚洲av伊人久久综合密臀性色| 91精品国产免费久久国语蜜臀| 久久久久亚洲av毛片大| 亚洲风情亚Aⅴ在线发布| 国产免费人人看大香伊| 中国一级毛片视频免费看| 亚洲男人都懂得羞羞网站| 成年人性生活免费视频| 日韩亚洲Av人人夜夜澡人人爽| 久久性生大片免费观看性| 4444亚洲国产成人精品| 免费无码毛片一区二区APP| 亚洲国产最大av| 亚洲人成电影网站国产精品| 中文字幕在线免费| 国产亚洲精品美女2020久久| 在线免费观看一级毛片| 亚洲性色AV日韩在线观看|