一、摘要

在集合系列的第一章，咱們了解到，Map 的實現類有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties等等。

應該有很多人不知道 IdentityHashMap 的存在，其中不乏工作很多年的 Java 開發者，本文主要從數據結構和算法層面，探討 IdentityHashMap 的實現。

二、簡介

IdentityHashMap 的數據結構很簡單，底層實際就是一個 Object 數組，但是在存儲上並沒有使用鏈表來存儲，而是將 K 和 V 都存放在 Object 數組上。

當添加元素的時候，會根據 Key 計算得到散列位置，如果發現該位置上已經有改元素，直接進行新值替換；如果沒有，直接進行存放。當元素個數達到一定閾值時，Object 數組會自動進行擴容處理。

打開 IdentityHashMap 的源碼，可以看到 IdentityHashMap 繼承了AbstractMap 抽象類，實現了Map接口、可序列化接口、可克隆接口。

public class IdentityHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, java.io.Serializable, Cloneable
{
    /**默認容量大小*/
    private static final int DEFAULT_CAPACITY = 32;
    
    /**最小容量*/
    private static final int MINIMUM_CAPACITY = 4;
    
    /**最大容量*/
    private static final int MAXIMUM_CAPACITY = 1 << 29;
    
    /**用於存儲實際元素的表*/
    transient Object[] table;
    
    /**數組大小*/
    int size;

    /**對Map進行結構性修改的次數*/
    transient int modCount;

    /**key為null所對應的值*/
    static final Object NULL_KEY = new Object();
    
    ......
}

可以看到類的底層，使用了一個 Object 數組來存放元素；在對象初始化時，IdentityHashMap 容量大小為64；

public IdentityHashMap() {
        //調用初始化方法
        init(DEFAULT_CAPACITY);
}

private void init(int initCapacity) {
        //數組大小默認為初始化容量的2倍
        table = new Object[2 * initCapacity];
}

三、常用方法介紹

3.1、put方法

put 方法是將指定的 key, value 對添加到 map 里。該方法首先會對map做一次查找，通過==判斷是否存在key，如果有，則將舊value返回，將新value覆蓋舊value；如果沒有，直接插入，數組長度+1，返回null。

源碼如下：

public V put(K key, V value) {
        //判斷key是否為空，如果為空，初始化一個Object為key
        final Object k = maskNull(key);

        retryAfterResize: for (;;) {
            final Object[] tab = table;
            final int len = tab.length;
            //通過key、length獲取數組小編
            int i = hash(k, len);
            
            //循環遍歷是否存在指定的key
            for (Object item; (item = tab[i]) != null;
                 i = nextKeyIndex(i, len)) {
                 //通過==判斷，是否數組中是否存在key
                if (item == k) {
                        V oldValue = (V) tab[i + 1];
                        //新value覆蓋舊value
                    tab[i + 1] = value;
                    //返回舊value
                    return oldValue;
                }
            }
            
            //數組長度 +1
            final int s = size + 1;
            //判斷是否需要擴容
            if (s + (s << 1) > len && resize(len))
                continue retryAfterResize;

            //更新修改次數
            modCount++;
            //將k加入數組
            tab[i] = k;
            //將value加入數組
            tab[i + 1] = value;
            size = s;
            return null;
        }
}

maskNull 函數，判斷 key 是否為空

private static Object maskNull(Object key) {
        return (key == null ? NULL_KEY : key);
}

hash 函數，通過 key 獲取 hash 值，結合數組長度通過位運算獲取數組散列下標

private static int hash(Object x, int length) {
        int h = System.identityHashCode(x);
        // Multiply by -127, and left-shift to use least bit as part of hash
        return ((h << 1) - (h << 8)) & (length - 1);
}

nextKeyIndex 函數，通過 hash 函數計算得到的數組散列下標，進行加2；因為一個 key、value 都存放在數組中，所以一個 map 對象佔用兩個數組下標，所以加2。

private static int nextKeyIndex(int i, int len) {
        return (i + 2 < len ? i + 2 : 0);
}

resize 函數，通過數組長度，進行擴容處理，擴容之後的長度為當前長度的2倍

private boolean resize(int newCapacity) {
        //擴容后的數組長度，為當前數組長度的2倍
        int newLength = newCapacity * 2;

        Object[] oldTable = table;
        int oldLength = oldTable.length;
        if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
            if (size == MAXIMUM_CAPACITY - 1)
                throw new IllegalStateException("Capacity exhausted.");
            return false;
        }
        if (oldLength >= newLength)
            return false;

        Object[] newTable = new Object[newLength];
        //將舊數組內容轉移到新數組
        for (int j = 0; j < oldLength; j += 2) {
            Object key = oldTable[j];
            if (key != null) {
                Object value = oldTable[j+1];
                oldTable[j] = null;
                oldTable[j+1] = null;
                int i = hash(key, newLength);
                while (newTable[i] != null)
                    i = nextKeyIndex(i, newLength);
                newTable[i] = key;
                newTable[i + 1] = value;
            }
        }
        table = newTable;
        return true;
}

3.2、get方法

get 方法根據指定的 key 值返回對應的 value。同樣的，該方法會循環遍曆數組，通過==判斷是否存在key，如果有，直接返回value，因為 key、value 是相鄰的存儲在數組中，所以直接在當前數組下標+1，即可獲取 value；如果沒有找到，直接返回null。

值得注意的地方是，在循環遍歷中，是通過==判斷當前元素是否與key相同，如果相同，則返回value。咱們都知道，在 java 中，==對於對象類型參數，判斷的是引用地址，確切的說，是堆內存地址，所以，這裏判斷的是key的引用地址是否相同，如果相同，則返回對應的 value；如果不相同，則返回null。

源碼如下：

public V get(Object key) {
        Object k = maskNull(key);
        Object[] tab = table;
        int len = tab.length;
        int i = hash(k, len);
        
        //循環遍曆數組，直到找到key或者，數組為空為值
        while (true) {
            Object item = tab[i];
            //通過==判斷，當前數組元素與key相同
            if (item == k)
                return (V) tab[i + 1];
            //數組為空
            if (item == null)
                return null;
            i = nextKeyIndex(i, len);
        }
}

3.3、remove方法

remove 的作用是通過 key 刪除對應的元素。該方法會循環遍曆數組，通過==判斷是否存在key，如果有，直接將key、value設置為null，對數組進行重新排列，返回舊 value。

源碼如下：

public V remove(Object key) {
        Object k = maskNull(key);
        Object[] tab = table;
        int len = tab.length;
        int i = hash(k, len);

        while (true) {
            Object item = tab[i];
            if (item == k) {
                modCount++;
                //數組長度減1
                size--;
                    V oldValue = (V) tab[i + 1];
                //將key、value設置為null
                tab[i + 1] = null;
                tab[i] = null;
                //刪除該元素后，需要把原來有衝突往後移的元素移到前面來
                closeDeletion(i);
                return oldValue;
            }
            if (item == null)
                return null;
            i = nextKeyIndex(i, len);
        }
}

closeDeletion 函數，刪除該元素后，需要把原來有衝突往後移的元素移到前面來，對數組進行重寫排列；

private void closeDeletion(int d) {
        // Adapted from Knuth Section 6.4 Algorithm R
        Object[] tab = table;
        int len = tab.length;

        Object item;
        for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
             i = nextKeyIndex(i, len) ) {
            int r = hash(item, len);
            if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
                tab[d] = item;
                tab[d + 1] = tab[i + 1];
                tab[i] = null;
                tab[i + 1] = null;
                d = i;
            }
        }
}

四、總結

1. IdentityHashMap 的實現不同於HashMap，雖然也是數組，不過IdentityHashMap中沒有用到鏈表，解決衝突的方式是計算下一個有效索引，並且將數據key和value緊挨着存在map中，即table[i]=key、table[i+1]=value；

2. IdentityHashMap 允許key、value都為null，當key為null的時候，默認會初始化一個Object對象作為key；

3. IdentityHashMap在保存、刪除、查詢數據的時候，以key為索引，通過==來判斷數組中元素是否與key相同，本質判斷的是對象的引用地址，如果引用地址相同，那麼在插入的時候，會將value值進行替換；

IdentityHashMap 測試例子：

public static void main(String[] args) {
        Map<String, String> identityMaps = new IdentityHashMap<String, String>();

        identityMaps.put(new String("aa"), "aa");
        identityMaps.put(new String("aa"), "bb");
        identityMaps.put(new String("aa"), "cc");
        identityMaps.put(new String("aa"), "cc");
        //輸出添加的元素
        System.out.println("數組長度："+identityMaps.size() + "，輸出結果：" + identityMaps);
    }

輸出結果：

數組長度：4，輸出結果：{aa=aa, aa=cc, aa=bb, aa=cc}

儘管key的內容是一樣的，但是key的堆地址都不一樣，所以在插入的時候，插入了4條記錄。

五、參考

1、JDK1.7&JDK1.8 源碼

2、

3、

作者：炸雞可樂
出處：

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※高價3c回收,收購空拍機,收購鏡頭,收購 MACBOOK-更多收購平台討論專區

※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享

※收購3c瘋!各款手機、筆電、相機、平板,歡迎來詢價!

※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選

鈣素

Canvas 是在HTML5中新增的標籤用於在網頁實時生成圖像，並且可以操作圖像內容，基本上它是一個可以用JavaScript操作的位圖。也就是說我們將通過JS完成畫圖而不是css。

canvas 默認布局為 inline-block，可以認為是一種特殊的圖片。

走起 ~

canvas 劃線

<canvas id="can" width="800" height="800"></canvas>

（寬高不能放在style裏面，否則比例不對）

canvas裏面的width和height相當於圖片的原始尺寸，加了外部style的寬高，就相當於對圖片進行壓縮和拉伸。

// 1、獲取原生dom對象
let dom = document.getElementById('can');

// 2、獲取繪圖對象
let can = dom.getContext('2d'); // 3d是webgl

// 定義線條起點
can.moveTo(0,0);

// 定義線條中點（非終點）
can.lineTo(400,400);
can.lineTo(800,0);

// 對標記範圍進行描邊
can.stroke()

// 對標記範圍進行填充
can.fill();

設置線條屬性

線條默認寬度是 1。

（一定要在繪圖之前設置。）

can.lineWidth = 2; //設置線條寬度
can.strokeStyle = '#f00';  // 設置線條顏色

can.fillStyle = '#f00';  // 設置填充區域顏色

折線樣式

• miter：尖角（當尖角長度值過長時會自動變成折角，如果強制显示尖角：can.miterLimit = 100 設置尖角長度閾值。
• round：圓角
• bevel：折角

can.lineJoin = 'miter';
can.moveTo(100, 100);
can.lineTo(300, 100);
can.lineTo(100, 200);
can.stroke()

can.lineJoin = 'round';
can.moveTo(400, 100);
can.lineTo(600, 100);
can.lineTo(400, 200);
can.stroke()

can.lineJoin = 'bevel';
can.moveTo(700, 100);
can.lineTo(900, 100);
can.lineTo(700, 200);
can.stroke()

設置線帽

• round：加圓角線帽
• square：加直角線帽
• butt：不加線帽

    can.lineCap = 'round';
    can.moveTo(100, 100);
    can.lineTo(300, 100);
    can.stroke()
    
     // 新建繪圖，使得上一次的繪畫樣式不會影響下面的繪畫樣式（代碼加在上一次繪畫和下一次繪畫中間。）
    can.beginPath()
    
    can.lineCap = 'square';
    can.moveTo(100, 200);
    can.lineTo(300, 200);
    can.stroke()
    
    can.beginPath()
    
    can.lineCap = 'butt';
    can.moveTo(100, 300);
    can.lineTo(300, 300);
    can.stroke()

畫矩形

// 參數：x,y,寬，高

can.rect(100,100,100,100);
can.stroke();

// 畫完即填充
can.fillRect(100,100,100,100);

畫圓弧

// 參數：圓心x，圓心y，半徑，圓弧起點與圓心的夾角度數，圓弧終點與圓心的夾角度數，true（逆時針繪畫）

can.arc(500,300,200,0,2*Math.PI/360*90,false);
can.stroke()

示例：

can.moveTo(500,300);
can.lineTo(500 + Math.sqrt(100), 300 + Math.sqrt(100))
can.arc(500, 300, 100, 2 * Math.PI / 360 *startDeg, 2 * Math.PI / 360 *endDeg, false);
can.closePath()//將圖形起點和終點用線連接起來使之成為封閉的圖形
can.fill()

Tips:

1、can.beginPath() // 新建繪圖，使得上一次的繪畫樣式不會影響下面的繪畫樣式（代碼加在上一次繪畫和下一次繪畫中間。）

2、can.closePath() //將圖形起點和終點用線連接起來使之成為封閉的圖形。

旋轉畫布

can.rotate(2*Math.PI/360*45); // 一定要寫在開始繪圖之前
can.fillRect(0,0,200, 10);

旋轉整個畫布的坐標系（參考坐標為畫布的(0,0)位置）

縮放畫布

can.scale(0.5,2);
can.fillRect(0,0,200, 10);

示例：

整個畫布：x方向縮放為原來的0.5，y方向拉伸為原來的2倍。

畫布位移

can.translate(100,100)
can.fillRect(0,0,200, 10);

保存與恢復畫布狀態

can.save() // 存檔：保存當前畫布坐標系狀態
can.restore() // 讀檔：恢復之前保存的畫布坐標系狀態

需要正確坐標系繪圖的時候，再讀檔之前的正確坐標系。

can.restore() // 將當前的畫布坐標系狀態恢復成上一次保存時的狀態
can.fillRect(dom.width/2, dom.height/2, 300, 100)

指針時鐘（案例）

<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>clock</title>
    <style type="text/css">
        #can {
            width: 1000px;
            height: 600px;
            background: linear-gradient(45deg, green, skyblue);
        }
    </style>
</head>

<body>
    <canvas id="can" width="2000" height="1200"></canvas>
</body>

<script type="text/javascript">
    let dom = document.getElementById('can');

    let can = dom.getContext('2d');

    // 把畫布的圓心移動到畫布的中心
    can.translate(dom.width / 2, dom.height / 2);
    // 保存當前的畫布坐標系
    can.save()


    run();



    function run() {
        setInterval(function() {
            clearCanvas();
            draw();
        }, 10);
    }

    // 繪圖
    function draw() {
        let time = new Date();
        let hour = time.getHours();
        let min = time.getMinutes();
        let sec = time.getSeconds();
        let minSec = time.getMilliseconds();

        drawPannl();
        drawHour(hour, min, sec);
        drawMin(min, sec);
        drawSec(sec, minSec);
        drawPoint();
    }

    // 最簡單的方法：由於canvas每當高度或寬度被重設時，畫布內容就會被清空
    function clearCanvas() {
        dom.height = dom.height;
        can.translate(dom.width / 2, dom.height / 2);
        can.save()
    }

    // 畫錶盤
    function drawPannl() {
        can.beginPath();

        can.restore()
        can.save()

        can.lineWidth = 10;
        can.strokeStyle = 'skyblue';
        can.arc(0, 0, 400, 0, 2 * Math.PI);
        can.stroke();

        for (let i = 0; i < 12; i++) {
            can.beginPath();
            can.lineWidth = 16;
            can.strokeStyle = 'greenyellow';

            can.rotate(2 * Math.PI / 12)

            can.moveTo(0, -395);
            can.lineTo(0, -340);
            can.stroke();
        }

        for (let i = 0; i < 60; i++) {
            can.beginPath();
            can.lineWidth = 10;
            can.strokeStyle = '#fff';

            can.rotate(2 * Math.PI / 60)

            can.moveTo(0, -395);
            can.lineTo(0, -370);
            can.stroke();
        }
    }

    // 畫時針
    function drawHour(h, m, s) {
        can.beginPath();

        can.restore()
        can.save()

        can.lineWidth = 24;
        can.strokeStyle = 'palevioletred';
        can.lineCap = 'round'
        can.rotate(2 * Math.PI / (12 * 60 * 60) * (h * 60 * 60 + m * 60 + s))
        can.moveTo(0, 0);
        can.lineTo(0, -200);
        can.stroke();
    }

    // 畫分針
    function drawMin(m, s) {
        can.beginPath();

        can.restore()
        can.save()

        can.lineWidth = 14;
        can.strokeStyle = '#09f';
        can.lineCap = 'round'
        can.rotate(2 * Math.PI / (60 * 60) * (m * 60 + s))
        can.moveTo(0, 0);
        can.lineTo(0, -260);
        can.stroke();
    }

    // 畫秒針
    function drawSec(s, ms) {
        can.beginPath();

        can.restore()
        can.save()

        can.lineWidth = 8;
        can.strokeStyle = '#f00';
        can.lineCap = 'round'
        can.rotate(2 * Math.PI / (60 * 1000) * (s * 1000 + ms));
        can.moveTo(0, 50);
        can.lineTo(0, -320);
        can.stroke();
    }


    // 畫中心點
    function drawPoint() {
        can.beginPath();

        can.restore()
        can.save()

        can.lineWidth = 10;
        can.fillStyle = 'red';
        can.arc(0, 0, 12, 0, 2 * Math.PI);
        can.fill();
    }
</script>

</html>

圓弧時鐘（案例）

<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>clock</title>
    <style type="text/css">
        #can {
            width: 1000px;
            height: 600px;
            background: linear-gradient(45deg, rgb(94, 53, 6), black);
        }
    </style>
</head>

<body>
    <canvas id="can" width="2000" height="1200"></canvas>
</body>

<script type="text/javascript">
    let dom = document.getElementById('can');

    let can = dom.getContext('2d');

    // 把畫布的圓心移動到畫布的中心
    can.translate(dom.width / 2, dom.height / 2);
    // 保存當前的畫布坐標系
    can.save();

    // 圓形指針起始角度
    let startDeg = 2 * Math.PI / 360 * 270;


    run();
    // draw();


    function run() {
        setInterval(function() {
            clearCanvas();
            draw();
        }, 20);
    }

    // 繪圖
    function draw() {
        let time = new Date();
        // let hour = time.getHours();
        let hour = time.getHours() > 10 ? time.getHours() - 12 : time.getHours();
        let min = time.getMinutes();
        let sec = time.getSeconds();
        let minSec = time.getMilliseconds();

        drawPannl();
        drawTime(hour, min, sec, minSec);
        drawHour(hour, min, sec);
        drawMin(min, sec);
        drawSec(sec, minSec);
        drawPoint();
    }

    // 最簡單的方法：由於canvas每當高度或寬度被重設時，畫布內容就會被清空
    function clearCanvas() {
        dom.height = dom.height;
        can.translate(dom.width / 2, dom.height / 2);
        can.save()
    }

    // 畫錶盤
    function drawPannl() {

        can.restore()
        can.save()

        // 設置時錶盤
        can.beginPath();
        can.lineWidth = 50;
        can.strokeStyle = 'rgba(255,23,87,0.2)';
        can.arc(0, 0, 400, 0, 2 * Math.PI);
        can.stroke();
        // 設置分錶盤
        can.beginPath();
        can.strokeStyle = 'rgba(169,242,15,0.2)';
        can.arc(0, 0, 345, 0, 2 * Math.PI);
        can.stroke();
        // 設置秒錶盤
        can.beginPath();
        can.strokeStyle = 'rgba(21,202,230,0.2)';
        can.arc(0, 0, 290, 0, 2 * Math.PI);
        can.stroke();


        // 小時刻度
        // for (let i = 0; i < 12; i++) {
        //     can.beginPath();
        //     can.lineWidth = 16;
        //     can.strokeStyle = 'rgba(0,0,0,0.2)';

        //     can.rotate(2 * Math.PI / 12)

        //     can.moveTo(0, -375);
        //     can.lineTo(0, -425);
        //     can.stroke();
        // }

        // 分針刻度
        // for (let i = 0; i < 60; i++) {
        //     can.beginPath();
        //     can.lineWidth = 10;
        //     can.strokeStyle = '#fff';

        //     can.rotate(2 * Math.PI / 60)

        //     can.moveTo(0, -395);
        //     can.lineTo(0, -370);
        //     can.stroke();
        // }
    }

    // 畫時針
    function drawHour(h, m, s) {

        let rotateDeg = 2 * Math.PI / (12 * 60 * 60) * (h * 60 * 60 + m * 60 + s);

        can.beginPath();
        can.restore()
        can.save()

        // 時針圓弧
        can.lineWidth = 50;
        can.strokeStyle = 'rgb(255,23,87)';
        can.lineCap = 'round';
        can.shadowColor = "rgb(255,23,87)"; // 設置陰影顏色
        can.shadowBlur = 20; // 設置陰影範圍
        can.arc(0, 0, 400, startDeg, startDeg + rotateDeg);
        can.stroke();

        // 時針指針
        can.beginPath();
        can.lineWidth = 24;
        can.strokeStyle = 'rgb(255,23,87)';
        can.lineCap = 'round'
        can.rotate(rotateDeg)
        can.moveTo(0, 0);
        can.lineTo(0, -100);
        can.stroke();



    }

    // 畫分針
    function drawMin(m, s) {

        let rotateDeg = 2 * Math.PI / (60 * 60) * (m * 60 + s);

        can.beginPath();
        can.restore()
        can.save()

        // 分針圓弧
        can.lineWidth = 50;
        can.strokeStyle = 'rgb(169,242,15)';
        can.lineCap = 'round'
        can.shadowColor = "rgb(169,242,15)";
        can.shadowBlur = 20;
        can.arc(0, 0, 345, startDeg, startDeg + rotateDeg);
        can.stroke();

        // 分針指針
        can.beginPath();
        can.lineWidth = 14;
        can.strokeStyle = 'rgb(169,242,15)';
        can.lineCap = 'round'
        can.rotate(rotateDeg)
        can.moveTo(0, 0);
        can.lineTo(0, -160);
        can.stroke();
    }

    // 畫秒針
    function drawSec(s, ms) {

        let rotateDeg = 2 * Math.PI / (60 * 1000) * (s * 1000 + ms);

        can.beginPath();
        can.restore()
        can.save()

        can.lineWidth = 50;
        can.strokeStyle = 'rgb(21,202,230)';
        can.lineCap = 'round'
        can.arc(0, 0, 290, startDeg, startDeg + rotateDeg);
        can.stroke();

        can.beginPath();
        can.lineWidth = 8;
        can.strokeStyle = 'rgb(21,202,230)';
        can.lineCap = 'round'
        can.shadowColor = "rgb(21,202,230)";
        can.shadowBlur = 20;
        can.rotate(rotateDeg);
        can.moveTo(0, 50);
        can.lineTo(0, -220);
        can.stroke();
    }


    // 畫中心點
    function drawPoint() {
        can.beginPath();
        can.restore()
        can.save()

        can.lineWidth = 10;
        can.fillStyle = 'red';
        can.arc(0, 0, 12, 0, 2 * Math.PI);
        can.fill();
    }

    // 显示数字時鐘
    function drawTime(h, m, s, ms) {
        can.font = '60px Calibri';
        can.fillStyle = '#0f0'
        can.shadowColor = "#fff";
        can.shadowBlur = 20;
        can.fillText(`${h}:${m}:${s}.${ms}`, -140, -100);
    }
</script>

</html>

（啾咪 ^.<）

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※高價3c回收,收購空拍機,收購鏡頭,收購 MACBOOK-更多收購平台討論專區

※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享

※收購3c瘋!各款手機、筆電、相機、平板,歡迎來詢價!

※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選

之前我們介紹過BERT+CRF來進行命名實體識別，並對其中的BERT和CRF的概念和作用做了相關的介紹，然對於CRF中的最優的標籤序列的計算原理，我們只提到了維特比算法，並沒有做進一步的解釋，本文將對維特比算法做一個通俗的講解，以便大家更好的理解CRF為什麼能夠得到最優的標籤序列。

通過閱讀本文你將能回答如下問題：

• 什麼是維特比算法？
• 為什麼說維特比算法是一種動態規劃算法？
• 維特比算法具體怎麼實現？

首先，讓我們簡單回顧一下BERT和CRF在命名實體識別中各自的作用：
命名實體識別中，BERT負責學習輸入句子中每個字和符號到對應的實體標籤的規律，而CRF負責學習相鄰實體標籤之間的轉移規則。詳情可以參考這篇文章。該文章中我們對CRF做了簡單易懂的介紹，其中提到CRF的損失函數計算要用到最優路徑，因為CRF的損失函數是求最優路徑的概率占所有路徑概率和的比例，而我們的目標是最大化這個比例。那麼這裏就涉及到計算最優路徑的問題。這裏的路徑在命名實體識別的例子中，就是最終輸出的與句子中的字或符號一 一對應的標籤序列。不同標籤序列的順序組成了不同的路徑。而CRF就是要找出最正確的那條標籤序列路徑，也就是說這條標籤路徑的概率將是所有路徑中最大的，那麼我們可以窮舉出所有可能的標籤路徑，計算出每條路徑的概率和，然後比較出最大的那條，但是這樣做的代價太大了，所以crf選擇了一種稱為維特比的算法來求解此類問題。

維特比算法（英語：Viterbi algorithm）是一種動態規劃算法。它用於尋找最有可能產生觀測事件序列的維特比路徑。

看看下面這個命名實體識別的例子：

上圖共有5層(觀測序列的長度)，每層3個節點(狀態的個數)，我們的目標就是找到從第一層到第五層的最優路徑。
首先，我們分別計算紅、黃、藍三個節點的輸入連線的概率，以紅色節點舉例，我們先假設紅色節點在最優路徑上，那麼輸入到該節點的三條連線中，概率最大的那條一定在最優路徑上，同理，我們再分別假設黃色和藍色節點在最優路徑上，我們也能各找到一條概率最大的連線，這樣就得到了下面的圖：

然後，我們接着剛才的思路繼續找後面一層的三條最優的連線：

假設找到的最優連線如下：

然後，接着在後面的層應用這個方法：

此時，看上面最後一張圖，我們有了3條候選最優路徑，分別是棕色、綠色和紫色，用標籤來表達如下：

那麼哪條才是最優路徑呢？
就是看哪條路徑的概率和最大，那條路徑就是最優路徑。
但是在實際實現的時候，一般會在計算各層的最優候選連線的時候，就記錄下前繼連線的概率和，並記錄下對應的狀態節點索引(這裏將已經計算出的結果記錄下來供後續使用的方式，就是維特比算法被稱為動態規劃算法的原因)，這樣到最後一層的時候，最後一層各候選連線中概率最大的，就是在最優路徑上的那條連線了，然後從這條連線回溯，找出完整的路徑就是最優路徑了。

一直在說概率最大的路徑，那麼這個概率具體指什麼呢？
還記得上一篇文章介紹條件隨機場(CRF)的時候提到，條件隨機場其實是給定了觀測序列的馬爾可夫隨機場，在一階馬爾可夫模型中，定義了以下三個概念：

• 狀態集合Q，對應到上面的例子就是：
  {B-P, I-P, O}
• 初始狀態概率向量Π，對應到上面的例子就是：
  {B-P:0.3, I-P:0.2, O:0.5}
  這裏的概率數值是隨便假設的，僅為了方便舉例說明。
• 狀態轉移概率矩陣A：

CRF中給定了觀測序列做為先驗條件，對應到上面的例子就是：

其中的概率數值同樣是隨便假設的，為了方便舉例。

下圖中紅色節點的概率(可以看成是一個虛擬的開始節點到該節點的連線的概率)的計算方式如下：
初始狀態為B-P的概率Π(B-P) * 該節點的觀測概率P(小|B-P)

下圖中紅色節點的三條連線概率的計算方式如下：
上一層對應節點的概率 * 上層對應節點到該節點的轉移概率 * 該節點的觀測概率P(明|B-P)

其它層之間的節點連線的概率同理計算可得，然後通過上面介紹的維特比算法過程就可以計算出最優路徑了。

ok,本篇就這麼多內容啦~，感謝閱讀O(∩_∩)O。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※高價3c回收,收購空拍機,收購鏡頭,收購 MACBOOK-更多收購平台討論專區

※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享

※收購3c瘋!各款手機、筆電、相機、平板,歡迎來詢價!

※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選

此篇參考：

 我們在lightning中在前台會經常碰到獲取picklist的values然後使用select option進行渲染成下拉列表，此篇用於實現針對指定的sObject以及fieldName(Picklist類型)獲取此字段對應的所有可用的values的公用組件。因為不同的record type可能設置不同的picklist values，所以還有另外的參數設置針對指定的record type developer name去獲取指定的record type對應的Picklist values.

一. PicklistService公用組件聲明實現

Common_PicklistController.cls:有三個形參，其中objectName以及fieldName是必填參數，recordTypeDeveloperName為可選參數。

 1 public without sharing class Common_PicklistController {
 2     
 3     @AuraEnabled(cacheable=true)
 4     public static List<Map<String,String>> getPicklistValues(String objectName, String fieldName,String recordTypeDeveloperName) {
 5         //1. use object and field name get DescribeFieldResult and also get all the picklist values
 6         List<Schema.PicklistEntry> allPicklistValuesByField;
 7         try {
 8             List<Schema.DescribeSobjectResult> objDescriptions = Schema.describeSObjects(new List<String>{objectName});
 9             Schema.SObjectField field = objDescriptions[0].fields.getMap().get(fieldName);
10             Schema.DescribeFieldResult fieldDescribeResult = field.getDescribe();
11             allPicklistValuesByField = fieldDescribeResult.getPicklistValues();
12         } catch (Exception e) {
13             throw new AuraHandledException('Failed to retrieve values : '+ objectName +'.'+ fieldName +': '+ e.getMessage());
14         }
15         
16         //2. get all active field name -> label map
17         List<Map<String,String>> activeOptionMapList = new List<Map<String,String>>();
18         Map<String,String> optionValue2LabelMap = new Map<String,String>();
19         List<String> optionValueList;
20         for(Schema.PicklistEntry entry : allPicklistValuesByField) {
21             if (entry.isActive()) {
22                 System.debug(LoggingLevel.INFO, '*** entry: ' + JSON.serialize(entry));
23                 optionValue2LabelMap.put(entry.getValue(), entry.getLabel());
24             }
25         }
26 
27         //3. generate list with option value(with/without record type)
28         if(String.isNotBlank(recordTypeDeveloperName)) {
29             optionValueList = PicklistDescriber.describe(objectName,recordTypeDeveloperName,fieldName);
30         } else {
31             optionValueList = new List<String>(optionValue2LabelMap.keySet());
32         }
33 
34         //4. generate and format result
35         if(optionValueList != null) {
36             for(String option : optionValueList) {
37                 String optionLabel = optionValue2LabelMap.get(option);
38                 Map<String,String> optionDataMap = new Map<String,String>();
39                 optionDataMap.put('value',option);
40                 optionDataMap.put('label', optionLabel);
41                 activeOptionMapList.add(optionDataMap);
42             }
43         }
44 
45         return activeOptionMapList;
46     }
47 }

 Common_PicklistService.cmp:聲明了getPicklistInfo方法，有以下三個主要參數.objectName對應sObject的API名字，fieldName對應的此sObject中的Picklist類型的字段，recordTypeDeveloperName對應這個sObject的record type的developer name

1 <aura:component access="global" controller="Common_PicklistController">
2     <aura:method access="global" name="getPicklistInfo"  description="Retrieve active picklist values and labels mapping with(without) record type" action="{!c.getPicklistInfoAction}">
3         <aura:attribute type="String" name="objectName" required="true" description="Object name"/>
4         <aura:attribute type="String" name="fieldName" required="true" description="Field name"/>
5         <aura:attribute type="String" name="recordTypeDeveloperName" description="record type developer name"/>
6         <aura:attribute type="Function" name="callback" required="true" description="Callback function that returns the picklist values and labels mapping as [{value: String, label: String}]"/>
7     </aura:method>
8 </aura:component>

 Common_PicklistServiceController.js: 獲取傳遞過來的參數，調用後台方法並對結果放在callback中。

 1 ({
 2     getPicklistInfoAction : function(component, event, helper) {
 3         const params = event.getParam('arguments');
 4         const action = component.get('c.getPicklistValueList');
 5         action.setParams({
 6             objectName : params.objectName,
 7             fieldName : params.fieldName,
 8             recordTypeDeveloperName : params.recordTypeDeveloperName
 9         });
10         action.setCallback(this, function(response) {
11             const state = response.getState();
12             if (state === 'SUCCESS') {
13                 params.callback(response.getReturnValue());
14             } else if (state === 'ERROR') {
15                 console.error('failed to retrieve picklist values for '+ params.objectName +'.'+ params.fieldName);
16                 const errors = response.getError();
17                 if (errors) {
18                     console.error(JSON.stringify(errors));
19                 } else {
20                     console.error('Unknown error');
21                 }
22             }
23         });
24 
25         $A.enqueueAction(action);
26     }
27 })

二. 公用組件調用

 上面介紹了公用組件以後，下面的demo是如何調用。

SimplePicklistDemo引入Common_PicklistService，設置aura:id用於後期獲取到此component，從而調用方法

 1 <aura:component implements="flexipage:availableForAllPageTypes">
 2     <!-- include common picklist service component -->
 3     <c:Common_PicklistService aura:id="service"/>
 4     <aura:handler name="init" value="{!this}" action="{!c.doInit}"/>
 5 
 6     <aura:attribute name="accountTypeList" type="List"/>
 7     <aura:attribute name="accountTypeListByRecordType" type="List"/>
 8 
 9     <lightning:layout verticalAlign="center" class="x-large">
10         <lightning:layoutItem flexibility="auto" padding="around-small">
11             <lightning:select label="account type">
12                 <aura:iteration items="{!v.accountTypeList}" var="type">
13                     <option value="{!type.value}" text="{!type.label}"></option>
14                 </aura:iteration>
15             </lightning:select>
16         </lightning:layoutItem>
17 
18         <lightning:layoutItem flexibility="auto" padding="around-small">
19             <lightning:select label="account type with record type">
20                 <aura:iteration items="{!v.accountTypeListByRecordType}" var="type">
21                     <option value="{!type.value}" text="{!type.label}"></option>
22                 </aura:iteration>
23             </lightning:select>
24         </lightning:layoutItem>
25     </lightning:layout>
26     
27 </aura:component>

SimplePicklistDemoController.js：初始化方法用於獲取到公用組件component然後獲取Account的type的values，第一個是獲取所有的values/labels，第二個是獲取指定record type的values/labels。

 1 ({
 2     doInit : function(component, event, helper) {
 3         const service = component.find('service');
 4         service.getPicklistInfo('Account','type','',function(result) {
 5             component.set('v.accountTypeList', result);
 6         });
 7 
 8         service.getPicklistInfo('Account','type','Business_Account',function(result) {
 9             component.set('v.accountTypeListByRecordType',result);
10         });
11     }
12 })

三.效果展示：

1. account type的展示方式

 2. account type with record type的展示方式。

 總結：篇中介紹了Picklist values針對with/without record type的公用組件的使用，感興趣的可以進行優化，篇中有錯誤的歡迎指出，有不懂的歡迎留言。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※高價3c回收,收購空拍機,收購鏡頭,收購 MACBOOK-更多收購平台討論專區

※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享

※收購3c瘋!各款手機、筆電、相機、平板,歡迎來詢價!

※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選