版權(quán)申明

原創(chuàng)文章：本博所有原創(chuàng)文章，歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處，并聯(lián)系本人取得授權(quán)。
版權(quán)郵箱地址：banquan@mrdwy.com

問題難點(diǎn)

文本和數(shù)據(jù)的去重是經(jīng)常要用到的重要操作书在，普通數(shù)量的文本處理并不存在技術(shù)上的難點(diǎn)，可以直接在內(nèi)存中高效處理拆又，但是如果涉及到的文本量達(dá)到了數(shù)十億級別儒旬，直接在內(nèi)存中處理文本去重工作幾乎變成不可實(shí)現(xiàn)，例如假設(shè)有個文本中包含有20億手機(jī)號碼帖族，每個手機(jī)號碼共計11位數(shù)字栈源，int最大值只能保存2^31-1=2147483647，不夠表示手機(jī)號竖般，因此只能用String或者long型來表示手機(jī)號甚垦。

Java基本數(shù)據(jù)類型

byte?????????1字節(jié)
short????????2字節(jié)
int????????????4字節(jié)
long?????????8字節(jié)
char?????????2字節(jié)（C語言中是1字節(jié)）可以存儲一個漢字
float?????????4字節(jié)
double?????8字節(jié)
boolean???false/true(理論上占用1bit,1/8字節(jié)，實(shí)際處理按1byte處理)
那么用long類型一個手機(jī)號占用8字節(jié)，用String類型艰亮，則需要char[11]的字符數(shù)組來表示闭翩，占用2 * 11 = 22字節(jié)
20億則分別需要
long????????16,000,000,000字節(jié) = 14.9G
String??????44,000,000,000字節(jié) = 40.98G
如果去重操作直接將手機(jī)號加載到內(nèi)存中處理顯然是十分浪費(fèi)系統(tǒng)內(nèi)存的方式，況且需要如此大內(nèi)存的機(jī)器專門運(yùn)行去重操作迄埃，也非常不劃算疗韵，就算有這樣大內(nèi)存的機(jī)器供你使用，直接從幾十億文本中判斷字符串有沒有重復(fù)的計算量也是非常耗時的一個操作侄非，重復(fù)進(jìn)行幾十億次蕉汪，顯然這個時間量是無法接受的。

解決思路

數(shù)據(jù)結(jié)構(gòu)

大文本去重最優(yōu)的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是使用Bitmap彩库，那么具體要如何實(shí)現(xiàn)呢肤无？
簡單來說就是直接使用二進(jìn)制來表示手機(jī)號是否存在先蒋，一個byte類型占用1字節(jié)骇钦，用byte類型最多可以存儲8bit數(shù)據(jù)，也就是8個二進(jìn)制位竞漾，分別能夠表示8個數(shù)據(jù)是否存在眯搭，用0表示不存在1表示存在，那么理論上业岁，我們使用1個字符的內(nèi)存容量就可以表示8個手機(jī)號是否存在了鳞仙。
中國的手機(jī)號全部是1開頭，目前啟用了18笔时、17棍好、15、14允耿、13幾個號碼段借笙，甚至可以細(xì)分到3位，但為了簡便较锡，以及考慮到未來號碼擴(kuò)展业稼，我們簡略的直接只忽略1的開頭，用Bitmap來表示全部號碼是否存在只需要占用9,999,999,999個bit位也就是1,249,999,999.875 約等于 1,250,000,000 個字節(jié) = 1.164g的空間蚂蕴！
比起上一節(jié)的空間占用量是不是一個非常驚人的節(jié)約呢低散？

如何計算

我們可以直接申請一個1.165G存儲空間當(dāng)作手機(jī)的字典表，且所有位全部用0表示目前沒有任何號碼在我們的字典中骡楼。
字典的第0位表示手機(jī)號碼100 0000 0000 最后一位表示199 9999 9999熔号，如果文本中存在號碼100 0000 0000則將第一位改成1即可表示100 0000 0000號碼存在，依次類推鸟整。

運(yùn)算

因?yàn)镴ava中最小的數(shù)據(jù)類型為byte引镊，占用1字節(jié)，因此用二進(jìn)制表示為0000 0000，每一位分別有數(shù)據(jù)的表示我們可以定義一個數(shù)組如下：
0000 0001
0000 0010
0000 0100
0000 1000
0001 0000
0010 0000
0100 0000
1000 0000
為了方便我們將其轉(zhuǎn)化成10進(jìn)制則分別為
1, 2祠乃，4梦重，8，16亮瓷，32琴拧，64，-128（字節(jié)第一位為符號位）
那么每個字符嘱支，我們都可以表示為8個上述的二進(jìn)制數(shù)

新增手機(jī)號

我們現(xiàn)在需要新增一個133 3333 3333 的手機(jī)號如何運(yùn)算呢蚓胸？
首先去掉最頭1，則剩下33 3333 3333 將其除以 8 = 416,666,666 （取整） 也就是該手機(jī)號在整個字典表的第416,666,666個字符除师，然后將33 3333 3333 除以8 取模 = 5 表示該手機(jī)號在 416,666,666 的第5位沛膳，那么用二進(jìn)制表示這個字符表示應(yīng)該是0010 0000，運(yùn)算用或運(yùn)算 0000 0000 | 0010 0000 = 0010 0000
復(fù)雜情況如果該字符還有其他號碼存在例如原始字符為 0100 0000 | 0010 0000 = 0110 0000
證明用或運(yùn)算我們也可以完美的完成新增手機(jī)號的操作汛聚。

刪除手機(jī)號

我們再次用133 3333 3333 號碼舉例锹安，剛才我們已經(jīng)知道了該手機(jī)號在字典表的第416,666,666個字符的第5位，如何刪除呢：
1倚舀、求補(bǔ) 0010 0000 ^ 1111 1111 = 1101 1111
2叹哭、與操作 0010 0000 & 1101 1111 = 0000 0000
如果是其他號碼的結(jié)果 0110 0011 & 1101 1111 = 0100 0011
同樣可以完美的刪除該字符的第5位

判斷手機(jī)號是否存在

還是用剛才的例子 手機(jī)號133 3333 3333 在字典表的第416,666,666個字符的第5位，我們要判斷這個位置是否為1
這里有兩種算法都可以實(shí)現(xiàn)：
1痕貌、判斷 0010 0000 == 原始數(shù)據(jù) & 0010 0000 如果等式成立风罩，則表示該位置有號碼，否則沒有
演示
0000 0000 & 0010 0000 = 0000 0000 != 0010 0000 則沒有該號碼
0010 0000 & 0010 0000 = 0010 0000 == 0010 0000 則有該號碼
該字符有其他號碼的情況
1000 0000 & 0010 0000 = 0000 0000 != 0010 0000 該位置沒有該號碼
1010 0000 & 0010 0000 = 0010 0000 == 0010 0000 該位置有該號碼

2舵稠、判斷 1111 1111 == 原始數(shù)據(jù) | (0010 0000 ^ 1111 1111)
0000 0000 | 1101 1111 = 1101 1111 != 1111 1111 沒有號碼
0010 0000 | 1101 1111 = 1111 1111 == 1111 1111 有號碼
有其他號碼
1000 0000 | 1101 1111 = 1101 1111 != 1111 1111 沒有號碼
1010 0000 | 1101 1111 = 1111 1111 == 1111 1111 有號碼
以上我們完美的證明了兩種算法都可以表示是否存在某個手機(jī)號

算法實(shí)現(xiàn)代碼

package org.tcrow.datastructure;

import com.google.common.io.FileWriteMode;
import com.google.common.io.Files;

import javax.annotation.concurrent.ThreadSafe;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.regex.Pattern;

/**
 * @author tcrow.luo
 * @date 2018/8/27
 * @description BitMap處理手機(jī)號去重超升，支持海量手機(jī)號數(shù)據(jù)去重，處理時間毫秒級哺徊，理論上經(jīng)過改造可以支持更大的整數(shù)去重運(yùn)算室琢，但是初始化需要占用更多的存儲空間
 */
@ThreadSafe
public class Mobile {

    private final static int INIT_BUFFER_SIZE = 1024 * 1024;
    /**
     * 正則表達(dá)式：驗(yàn)證手機(jī)號
     */
    private final static String REGEX_MOBILE = "^((10[0-9])|(11[0-9])|(12[0-9])|(13[0-9])|(14[0-9])|(15[0-9])|(16[0-9])|(17[0-9])|(18[0-9])|(19[0-9]))\\d{8}$";

    /**
     * 二進(jìn)制1~8位分別為1的值，與原值進(jìn)行或操作即可完成在號碼庫的新增操作
     */
    private final static byte[] ARRAY_BYTE = {0b00000001, 0b00000010, 0b00000100, 0b00001000, 0b00010000, 0b00100000, 0b01000000, -0b10000000};


    /**
     * 二進(jìn)制掩碼唉工，-1 用二進(jìn)制表示 為 11111111
     * 因此任何字節(jié)異或掩碼后可以獲得取反值研乒，例如 00000001 ^ 11111111 = 11111110
     */
    private final static byte MASK_BYTE = -1;

    /**
     * 用于存儲手機(jī)號碼是否存在
     * 因?yàn)橹袊謾C(jī)號碼都是1開頭，所以第一位省略
     * 我們需要表示最大9999999999個號碼是否存在
     * 1字節(jié) = 8 bit 最多可以表示8個號碼
     * 因此需要空間 9999999999 / 8 = 1249999999.875 約等于 125 * 10 ^ 7 字節(jié) 約為 1.165 G 空間
     * 直接加載到內(nèi)存中比較浪費(fèi)淋硝，因此可以創(chuàng)建一個二進(jìn)制文件直接表示雹熬，然后通過RandomAccessFile類讀文件相應(yīng)的位
     */
    private File dictFile;

    private RandomAccessFile file;

    /**
     * 讀寫全局鎖，保證 讀讀共享, 讀寫互斥, 寫寫互斥
     */
    private final static ReadWriteLock LOCK = new ReentrantReadWriteLock();

    public Mobile(final String filePath) throws FileNotFoundException {
        dictFile = new File(filePath);
        if (!dictFile.exists()) {
            try {
                init();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        file = new RandomAccessFile(dictFile, "rw");
    }

    private void init() throws IOException {
        LOCK.writeLock().lock();
        try {
            Files.createParentDirs(dictFile);
            int loop = 1250000000 / INIT_BUFFER_SIZE + 1;
            byte[] buffer = new byte[INIT_BUFFER_SIZE];
            for (int i = 0; i < loop; i++) {
                Files.asByteSink(dictFile, FileWriteMode.APPEND).write(buffer);
            }
        } finally {
            LOCK.writeLock().unlock();
        }
    }

    /**
     * 新增電話號碼到字典中
     *
     * @param mobile
     */
    public void insert(String mobile) throws IOException {
        if (!isMobile(mobile)) {
            throwException(mobile);
        }
        if (hasMobile(mobile)) {
            return;
        }
        long no = Long.parseLong(mobile) - 10000000000L;
        int byteNum = (int) (no / 8);
        int bit = (int) (no % 8);
        byte b = read(byteNum);
        //對應(yīng)位或操作 e.g. 11100000 | 00000001 == 11100001 則成功插入了標(biāo)志位
        b = (byte) (b | ARRAY_BYTE[bit]);
        write(byteNum, b);
    }

    /**
     * 從字典中刪除電話號碼
     * @param mobile
     * @throws IOException
     */
    public void delete(String mobile) throws IOException {
        if (!isMobile(mobile)) {
            throwException(mobile);
        }
        if (!hasMobile(mobile)) {
            return;
        }
        long no = Long.parseLong(mobile) - 10000000000L;
        int byteNum = (int) (no / 8);
        int bit = (int) (no % 8);
        byte b = read(byteNum);
        //字節(jié)與操作 e.g. 00010001 & 11111110 == 00010000 則成功刪除了標(biāo)志位谣膳，對應(yīng)標(biāo)志位異或掩碼得對應(yīng)的補(bǔ)碼 e.g. 00000001 ^ 11111111 == 11111110
        b = (byte) (b & (ARRAY_BYTE[bit] ^ MASK_BYTE));
        write(byteNum, b);
    }

    private void throwException(String mobile) {
        throw new RuntimeException("The string \"" + mobile + "\" is not the mobile number.");
    }

    private void throwUnknownException() {
        throw new RuntimeException("read data unknown exception");
    }

    public boolean hasMobile(String mobile) throws IOException {
        if (!isMobile(mobile)) {
            throwException(mobile);
        }
        long no = Long.parseLong(mobile) - 10000000000L;
        int byteNum = (int) (no / 8);
        int bit = (int) (no % 8);
        byte b = read(byteNum);
        // 01000111 & 00000010 == 00000010   01000101 & 00000010 == 0
        // 10111111 | 11111101 == 11111111 == -1  10111101 | 11111101 == 11111101 != -1
        // 兩種判斷方式都可以實(shí)現(xiàn)竿报，取簡單的方式直接按位與操作后等于判斷位則表示標(biāo)志位有值
        if (ARRAY_BYTE[bit] == (byte) (b & ARRAY_BYTE[bit])) {
            return true;
        } else {
            return false;
        }
    }

    private boolean isMobile(String mobile) {
        return Pattern.matches(REGEX_MOBILE, mobile);
    }

    private byte read(int byteNum) throws IOException {
        LOCK.readLock().lock();
        byte[] buffer = new byte[1];
        try {
            file.seek(byteNum);
            int read = file.read(buffer);
            if (read <= 0) {
                throwUnknownException();
            }
        } finally {
            LOCK.readLock().unlock();
        }
        return buffer[0];
    }

    private void write(int byteNum, byte b) throws IOException {
        LOCK.writeLock().lock();
        try {
            file.seek(byteNum);
            byte[] buffer = new byte[1];
            buffer[0] = b;
            file.write(buffer);
        } finally {
            LOCK.writeLock().unlock();
        }
    }

}

我這邊為了節(jié)約內(nèi)存，字典是直接在外部存儲申請的空間继谚，操作上會比內(nèi)存中耗費(fèi)稍微多一點(diǎn)時間烈菌，因?yàn)橐x取外部存儲的數(shù)據(jù)，但相應(yīng)的可以對計算機(jī)內(nèi)存的需求度降低到最少，有了這個算法芽世，我們要實(shí)現(xiàn)海量手機(jī)號的去重就變得輕而易舉了挚赊。

延伸閱讀

bit-map主要用于對存儲空間大量壓縮的情況，例如其他字符文本的去重也是可以使用的济瓢，例如要進(jìn)行郵箱地址去重荠割，可以將郵箱地址進(jìn)行hash運(yùn)算得到等長的字符串，然后轉(zhuǎn)換成ascii碼旺矾，再存儲到bitmap中蔑鹦，就可以進(jìn)行郵箱地址的去重了。

再進(jìn)一步我們實(shí)際的場景中可能不止要對文本進(jìn)行去重箕宙，還得進(jìn)行熱點(diǎn)掃描嚎朽，例如百度的搜索熱點(diǎn)，這個可以使用到Trie樹的數(shù)據(jù)結(jié)構(gòu)柬帕，可以最快速的查找并獲得字典出現(xiàn)頻率哟忍，我這里貼上一個簡單的Trie樹的實(shí)現(xiàn)代碼。

package org.tcrow.datastructure;

import javax.annotation.concurrent.NotThreadSafe;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Trie樹
 *
 * @author tcrow.luo
 */
@NotThreadSafe
public class Trie {

    /**
     * 樹深度
     */
    private int depth = 0;

    /**
     * 節(jié)點(diǎn)總數(shù)
     */
    private int nodeNum = 0;

    /**
     * 子節(jié)點(diǎn)數(shù)雕崩，這里設(shè)置為支持全部ASCII碼178個字符魁索，如果確保輸入字符串只有字母可改為26個字符
     */
    private final int SIZE = 178;

    private TrieNode root;

    /**
     * 構(gòu)造Trie樹初始化數(shù)據(jù)
     */
    public Trie() {
        this.nodeNum = 0;
        this.depth = 0;
        this.root = new TrieNode();
    }


    /**
     * 子類節(jié)點(diǎn)
     */
    private class TrieNode {
        private int passed;
        private int ended;
        private boolean isEnd;
        private char value;
        private TrieNode parent;
        private TrieNode[] children;

        TrieNode() {
            this.passed = 0;
            this.ended = 0;
            this.children = new TrieNode[SIZE];
        }

        TrieNode(TrieNode parent) {
            this.passed = 0;
            this.ended = 0;
            this.parent = parent;
            this.children = new TrieNode[SIZE];
        }

    }


    /**
     * 插入字符串
     *
     * @param str
     * @return
     */
    public boolean insertStr(String str) {
        char[] strArr = str.toCharArray();
        TrieNode current = this.root;
        for (char c : strArr) {
            if (null == current.children[c]) {
                current.children[c] = new TrieNode(current);
                current.children[c].value = c;
                current.children[c].passed = 1;
                this.nodeNum++;
            } else {
                current.children[c].passed++;
            }
            current = current.children[c];
        }
        current.isEnd = true;
        current.ended++;
        if (strArr.length > this.depth) {
            this.depth = strArr.length;
        }

        return true;
    }

    /**
     * 統(tǒng)計字符串出現(xiàn)次數(shù)
     *
     * @param str
     * @return
     */
    public int countPrefix(String str) {
        TrieNode current = this.root;
        char[] strArr = str.toCharArray();
        for (char c : strArr) {
            if (null == current.children[c]) {
                return 0;
            } else {
                current = current.children[c];
            }

        }
        return current.ended;
    }

    /**
     * 統(tǒng)計出現(xiàn)次數(shù)最多的字符串
     *
     * @param rank 名次數(shù)
     * @return
     */
    public String[] tops(int rank) {
        TrieNode current = this.root;
        LinkedList<Integer> topTimes = new LinkedList<>();
        LinkedList<String> result = new LinkedList<>();
        ergodic(topTimes, result, current, rank);
        List<String> retList = new ArrayList<>();
        int length = rank > result.size() ? result.size() : rank;
        for (int i = 0; i < length; i++) {
            retList.add("單詞：" + result.get(i) + "，詞頻：" + topTimes.get(i));
        }
        return retList.toArray(new String[rank]);
    }


    /**
     * TOP統(tǒng)計遞歸
     *
     * @param topTimes 詞頻次數(shù)鏈表
     * @param result   字符串鏈表
     * @param current  當(dāng)前節(jié)點(diǎn)
     * @param rank     統(tǒng)計項目數(shù)
     */
    private void ergodic(LinkedList<Integer> topTimes, LinkedList<String> result, TrieNode current, int rank) {
        TrieNode[] children = current.children;
        for (TrieNode child : children) {
            if (null != child) {
                if (child.ended > 0) {
                    if (topTimes.size() == 0) {
                        topTimes.add(child.ended);
                        result.add(getStr(child));
                    } else {
                        for (int i = 0; i < topTimes.size(); i++) {
                            if (topTimes.get(i).intValue() > child.ended) {
                                continue;
                            }
                            topTimes.add(i, child.ended);
                            result.add(i, getStr(child));
                            if (topTimes.size() > rank) {
                                topTimes.removeLast();
                                result.removeLast();
                            }
                            break;
                        }
                    }
                }
                if (child.passed > 0) {
                    ergodic(topTimes, result, child, rank);
                }
            }
        }

    }

    /**
     * 獲取節(jié)點(diǎn)字符串
     *
     * @param current
     * @return
     */
    private String getStr(TrieNode current) {
        String str = new String(new char[]{current.value});
        if (this.root.equals(current.parent)) {
            return str;
        } else {
            return getStr(current.parent) + str;
        }
    }

    /**
     * 遍歷節(jié)點(diǎn)
     *
     * @param current
     */
    private void ergodic(TrieNode current) {
        TrieNode[] children = current.children;
        String word;
        for (TrieNode child : children) {
            if (null != child) {
                if (child.ended > 0) {
                    word = getStr(child);
                    System.out.println("單詞:" + word + ",詞頻:" + countPrefix(word));
                }
                if (child.passed > 0) {
                    ergodic(child);
                }
            }
        }
    }

    /**
     * 遍歷整個樹盼铁，打印出現(xiàn)的字符串
     */
    public void printAllStr() {
        TrieNode current = this.root;
        ergodic(current);
    }

}

好了本文結(jié)束，后續(xù)如果想學(xué)習(xí)更多算法和有意思的算法題目的實(shí)現(xiàn)尝偎，可以star我的github項目饶火，地址如下：
https://github.com/tcrow/algorithm

large-895567_640.jpg