首頁猿問文章關(guān)鍵字替換的問題

文章關(guān)鍵字替換的問題

心有法竹 2018-07-23 09:06:16

現(xiàn)在有一個字典key 是關(guān)鍵字名稱value 是關(guān)鍵字的鏈接地址發(fā)一篇文章如何高效的替換關(guān)鍵字為對應(yīng)的文章并且只替換一次呢？并且已經(jīng)是處于鏈接中的字不參與替換這種需求很多新聞網(wǎng)站都用得到不知道各位有沒有好的辦法！

查看完整描述

3 回答

叮當(dāng)貓咪

TA貢獻1776條經(jīng)驗獲得超12個贊

按照常規(guī)匹配，把長度為M的字典中的key都枚舉出來，然后從長度為N的文章中搜索關(guān)鍵詞，找到則替換。搜索的時間復(fù)雜度是O(M*N)。替換的時間復(fù)雜度取決于字典的查找速度和匹配到關(guān)鍵詞的個數(shù)，假設(shè)字典的時間復(fù)雜度是最理想狀況O(1)，要替換的關(guān)鍵字個數(shù)為K，那么替換的時間復(fù)雜度就是O(K)，如果通過數(shù)組存儲整篇文章還需要調(diào)整位置，則為O(K*N)。這樣最好情況下的復(fù)雜度就是O(M*N + K*N)。再按照樓主200個關(guān)鍵字，一篇平常的5000字文章需要搜索1百萬次。假設(shè)有10處替換項，保守估計需要5萬次的操作。

這樣算來，如果文章較長再加字典中關(guān)鍵詞多，那就指數(shù)級增長。對于文章本身，可以中文分詞后再匹配，會降低復(fù)雜度。對于字典，可以嘗試使用其它數(shù)據(jù)結(jié)構(gòu)，例如trie樹等。

反對回復(fù) 2018-07-25