基于布隆過濾器實作敏感詞識别和過濾

在目前的網絡環境下，敏感詞過濾已經是各大網站的“标準配置”，如果不想被大量的垃圾資訊充斥，除了使用機器人識别、驗證碼等驗證工具，還需要阻止含有敏感詞内容的釋出，否則可能面臨關站等風險，可謂是國内網際網路的紅線。

布隆過濾器

布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列随機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識别率和删除困難。

敏感詞的過濾，在程式設計中最常見的方法是敏感詞庫數組周遊比對，如果敏感詞在文本中出現，則視為違規。本文将介紹基于分詞技術和布隆過濾器實作的敏感詞檢測。相比于其它的資料結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數（O(k)）。另外，散列函數互相之間沒有關系，友善由硬體并行實作。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。除了敏感詞過濾，布隆過濾器還有以下應用場景：

1. 字處理軟體中，需要檢查一個英語單詞是否拼寫正确
2. 在 FBI，一個嫌疑人的名字是否已經在嫌疑名單上
3. 在網絡爬蟲裡，一個網址是否被通路過
4. yahoo, gmail等郵箱垃圾郵件過濾功能

布隆過濾器的原理

布隆過濾器（Bloom Filter）的核心實作是一個超大的位數組和幾個哈希函數。假設位數組的長度為m，哈希函數的個數為k

以上圖為例，具體的操作流程：假設集合裡面有3個元素{x, y, z}，哈希函數的個數為3。首先将位數組進行初始化，将裡面每個位都設定位0。對于集合裡面的每一個元素，将元素依次通過3個哈希函數進行映射，每次映射都會産生一個哈希值，這個值對應位數組上面的一個點，然後将位數組對應的位置标記為1。查詢W元素是否存在集合中的時候，同樣的方法将W通過哈希映射到位數組上的3個點。如果3個點的其中有一個點不為1，則可以判斷該元素一定不存在集合中。反之，如果3個點都為1，則該元素可能存在集合中。注意：此處不能判斷該元素是否一定存在集合中，可能存在一定的誤判率。可以從圖中可以看到：假設某個元素通過映射對應下标為4，5，6這3個點。雖然這3個點都為1，但是很明顯這3個點是不同元素經過哈希得到的位置，是以這種情況說明元素雖然不在集合中，也可能對應的都是1，這是誤判率存在的原因。

基于Java的程式設計實作

Google提供的guava核心庫中，提供了布隆過濾器的實作。其中的敏感詞庫檔案，可以參考：

https://github.com/tenstone/textfilter

@Service
public class BloomFilterService {

    private BloomFilter<String> configuredFilter;

    private final BloomFilter<String> filter = BloomFilter.create(new Funnel<String>() {
        private static final long serialVersionUID = 1L;
        @Override
        public void funnel(String arg0, PrimitiveSink arg1) {

            arg1.putString(arg0, Charsets.UTF_8);
        }
    }, 1024*1024*32);

    /**
     * 讀取帶敏感詞的布隆過濾器
     *
     * @return
     * @throws IOException
     */
    public BloomFilter<String> getSensitiveWordsFilter() throws IOException {
        InputStreamReader read = null;
        BufferedReader bufferedReader = null;
        read = new InputStreamReader(this.getClass().getClassLoader().getResourceAsStream("SensitiveWords.txt"), StandardCharsets.UTF_8);
        bufferedReader = new BufferedReader(read);
        for (String txt = null; (txt = bufferedReader.readLine()) != null; ) {
            filter.put(txt);
        }
        this.configuredFilter = filter;
        return filter;
    }

    /**
     * 判斷一段文字中，是否包含敏感詞
     *
     * @param segments
     * @return
     */
    public Boolean segmentSensitiveFilterPassed(String[] segments) {
        if(configuredFilter == null){
            try {
                getSensitiveWordsFilter();
            }catch (IOException e){
                e.printStackTrace();
            }
        }
        Segment shortestSegment = new DijkstraSegment().enableCustomDictionary(false).enablePlaceRecognize(true).enableOrganizationRecognize(true);
        for(String segment :segments){
            List<Term> termList =  shortestSegment.seg(segment);
            for (Term term :termList){
                // 如果布隆過濾器中找到了對應的詞，則認為敏感檢測不通過
                if(configuredFilter.mightContain(term.word)){
                    log.info("檢測到敏感詞："+term.word);
                    throw new RuntimeException("檢測到敏感詞");
                }
            }
        }
        return true;
    }