欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C#實(shí)現(xiàn)前向最大匹、字典樹(分詞、檢索)的示例代碼

 更新時(shí)間:2020年05月15日 15:04:45   作者:Spring2Sun  
這篇文章主要介紹了C#實(shí)現(xiàn)前向最大匹、字典樹的示例代碼,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

  場景:現(xiàn)在有一個(gè)錯(cuò)詞庫,維護(hù)的是錯(cuò)詞和正確詞對(duì)應(yīng)關(guān)系。比如:錯(cuò)詞“我門”對(duì)應(yīng)的正確詞“我們”。然后在用戶輸入的文字進(jìn)行錯(cuò)詞校驗(yàn),需要判斷輸入的文字是否有錯(cuò)詞,并找出錯(cuò)詞以便提醒用戶,并且可以顯示出正確詞以便用戶確認(rèn),如果是錯(cuò)詞就進(jìn)行替換。

  首先想到的就是取出錯(cuò)詞List放在內(nèi)存中,當(dāng)用戶輸入完成后用錯(cuò)詞List來foreach每個(gè)錯(cuò)詞,然后查找輸入的字符串中是否包含錯(cuò)詞。這是一種有效的方法,并且能夠?qū)崿F(xiàn)。問題是錯(cuò)詞的數(shù)量比較多,目前有10多萬條,將來也會(huì)不斷更新擴(kuò)展。所以pass了這種方案,為了讓錯(cuò)詞查找提高速度就用了字典樹來存儲(chǔ)錯(cuò)詞。

字典樹

  Trie樹,即字典樹,又稱單詞查找樹或鍵樹,是一種樹形結(jié)構(gòu),是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串(但不僅限于字符串),所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是:最大限度地減少無謂的字符串比較。

Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來降低查詢時(shí)間的開銷以達(dá)到提高效率的目的。

通常字典樹的查詢時(shí)間復(fù)雜度是O(logL),L是字符串的長度。所以效率還是比較高的。而我們上面說的foreach循環(huán)則時(shí)間復(fù)雜度為O(n),根據(jù)時(shí)間復(fù)雜度來看,字典樹效率應(yīng)該是可行方案。

字典樹原理

  根節(jié)點(diǎn)不包含字符,除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符; 從根節(jié)點(diǎn)到某一節(jié)點(diǎn),路徑上經(jīng)過的字符連接起來,為該節(jié)點(diǎn)對(duì)應(yīng)的字符串; 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。

  比如現(xiàn)在有錯(cuò)詞:“我門”、“旱睡”、“旱起”。那么字典樹如下圖

  其中紅色的點(diǎn)就表示詞結(jié)束節(jié)點(diǎn),也就是從根節(jié)點(diǎn)往下連接成我們的詞。

  實(shí)現(xiàn)字典樹:

public class Trie
{
  private class Node
  {
    /// <summary>
    /// 是否單詞根節(jié)點(diǎn)
    /// </summary>
    public bool isTail = false;

    public Dictionary<char, Node> nextNode;

    public Node(bool isTail)
    {
      this.isTail = isTail;
      this.nextNode = new Dictionary<char, Node>();
    }
    public Node() : this(false)
    {
    }
  }

  /// <summary>
  /// 根節(jié)點(diǎn)
  /// </summary>
  private Node rootNode;
  private int size;
  private int maxLength;

  public Trie()
  {
    this.rootNode = new Node();
    this.size = 0;
    this.maxLength = 0;
  }

  /// <summary>
  /// 字典樹中存儲(chǔ)的單詞的最大長度
  /// </summary>
  /// <returns></returns>
  public int MaxLength()
  {
    return maxLength;
  }

  /// <summary>
  /// 字典樹中存儲(chǔ)的單詞數(shù)量
  /// </summary>
  public int Size()
  {
    return size;
  }

  /// <summary>
  /// 獲取字典樹中所有的詞
  /// </summary>
  public List<string> GetWordList()
  {
    return GetStrList(this.rootNode);
  }

  private List<string> GetStrList(Node node)
  {
    List<string> wordList = new List<string>();

    foreach (char nextChar in node.nextNode.Keys)
    {
      string firstWord = Convert.ToString(nextChar);
      Node childNode = node.nextNode[nextChar];

      if (childNode == null || childNode.nextNode.Count == 0)
      {
        wordList.Add(firstWord);
      }
      else
      {

        if (childNode.isTail)
        {
          wordList.Add(firstWord);
        }

        List<string> subWordList = GetStrList(childNode);
        foreach (string subWord in subWordList)
        {
          wordList.Add(firstWord + subWord);
        }
      }
    }

    return wordList;
  }

  /// <summary>
  /// 向字典中添加新的單詞
  /// </summary>
  /// <param name="word"></param>
  public void Add(string word)
  {
    //從根節(jié)點(diǎn)開始
    Node cur = this.rootNode;
    //循環(huán)遍歷單詞
    foreach (char c in word.ToCharArray())
    {
      //如果字典樹節(jié)點(diǎn)中沒有這個(gè)字母,則添加
      if (!cur.nextNode.ContainsKey(c))
      {
        cur.nextNode.Add(c, new Node());
      }
      cur = cur.nextNode[c];
    }
    cur.isTail = true;

    if (word.Length > this.maxLength)
    {
      this.maxLength = word.Length;
    }
    size++;
  }

  /// <summary>
  /// 查詢字典中某單詞是否存在
  /// </summary>
  /// <param name="word"></param>
  /// <returns></returns>
  public bool Contains(string word)
  {
    return Match(rootNode, word);
  }

  /// <summary>
  /// 查找匹配
  /// </summary>
  /// <param name="node"></param>
  /// <param name="word"></param>
  /// <returns></returns>
  private bool Match(Node node, string word)
  {
    if (word.Length == 0)
    {
      if (node.isTail)
      {
        return true;
      }
      else
      {
        return false;
      }
    }
    else
    {
      char firstChar = word.ElementAt(0);
      if (!node.nextNode.ContainsKey(firstChar))
      {
        return false;
      }
      else
      {
        Node childNode = node.nextNode[firstChar];
        return Match(childNode, word.Substring(1, word.Length - 1));
      }
    }
  }
}

  測試下:

  現(xiàn)在我們有了字典樹,然后就不能以字典樹來foreach,字典樹用于檢索。我們就以用戶輸入的字符串為數(shù)據(jù)源,去字典樹種查找是否存在錯(cuò)詞。因此需要對(duì)輸入字符串進(jìn)行取詞檢索。也就是分詞,分詞我們采用前向最大匹配。

前向最大匹配

  我們分詞的目的是將輸入字符串分成若干個(gè)詞語,前向最大匹配就是從前向后尋找在詞典中存在的詞。

  例子:我們假設(shè)maxLength= 3,即假設(shè)單詞的最大長度為3。實(shí)際上我們應(yīng)該以字典樹中的最大單詞長度,作為最大長度來分詞(上面我們的字典最大長度應(yīng)該是2)。這樣效率更高,為了演示匹配過程就假設(shè)maxLength為3,這樣演示的更清楚。

  用前向最大匹配來劃分“我們應(yīng)該早睡早起” 這句話。因?yàn)槲沂清e(cuò)詞匹配,所以這句話我改成“我門應(yīng)該旱睡旱起”。

  第一次:取子串 “我門應(yīng)”,正向取詞,如果匹配失敗,每次去掉匹配字段最后面的一個(gè)字。

  “我門應(yīng)”,掃描詞典中單詞,沒有匹配,子串長度減 1 變?yōu)椤拔议T”。

  “我門”,掃描詞典中的單詞,匹配成功,得到“我門”錯(cuò)詞,輸入變?yōu)椤皯?yīng)該旱”。

  第二次:取子串“應(yīng)該旱”

  “應(yīng)該旱”,掃描詞典中單詞,沒有匹配,子串長度減 1 變?yōu)椤皯?yīng)該”。

  “應(yīng)該”,掃描詞典中的單詞,沒有匹配,輸入變?yōu)椤皯?yīng)”。

  “應(yīng)”,掃描詞典中的單詞,沒有匹配,輸入變?yōu)椤霸摵邓薄?/p>

  第三次:取子串“該旱睡”

  “該旱睡”,掃描詞典中單詞,沒有匹配,子串長度減 1 變?yōu)椤霸摵怠薄?/p>

  “該旱”,掃描詞典中的單詞,沒有匹配,輸入變?yōu)椤霸摗薄?/p>

  “該”,掃描詞典中的單詞,沒有匹配,輸入變?yōu)椤昂邓怠薄?/p>

  第四次:取子串“旱睡旱”

  “旱睡旱”,掃描詞典中單詞,沒有匹配,子串長度減 1 變?yōu)椤昂邓薄?/p>

  “旱睡”,掃描詞典中的單詞,匹配成功,得到“旱睡”錯(cuò)詞,輸入變?yōu)椤霸缙稹薄?/p>

  以此類推,我們得到錯(cuò)詞 我們/旱睡/旱起。

  因?yàn)槲沂墙Y(jié)合字典樹匹配錯(cuò)詞所以一個(gè)字也可能是錯(cuò)字,則匹配到單個(gè)字,如果只是分詞則上面的到一個(gè)字的時(shí)候就應(yīng)該停止分詞了,直接字符串長度減1。

  這種匹配方式還有后向最大匹配以及雙向匹配,這個(gè)大家可以去了解下。

  實(shí)現(xiàn)前向最大匹配,這里后向最大匹配也可以一起實(shí)現(xiàn)。

public class ErrorWordMatch
  {
    private static ErrorWordMatch singleton = new ErrorWordMatch();
    private static Trie trie = new Trie();
    private ErrorWordMatch()
    {

    }

    public static ErrorWordMatch Singleton()
    {
      return singleton;
    }

    public void LoadTrieData(List<string> errorWords)
    {
      foreach (var errorWord in errorWords)
      {
        trie.Add(errorWord);
      }
    }

    /// <summary>
    /// 最大 正向/逆向 匹配錯(cuò)詞
    /// </summary>
    /// <param name="inputStr">需要匹配錯(cuò)詞的字符串</param>
    /// <param name="leftToRight">true為從左到右分詞,false為從右到左分詞</param>
    /// <returns>匹配到的錯(cuò)詞</returns>
    public List<string> MatchErrorWord(string inputStr, bool leftToRight)
    {
      if (string.IsNullOrWhiteSpace(inputStr))
        return null;
      if (trie.Size() == 0)
      {
        throw new ArgumentException("字典樹沒有數(shù)據(jù),請(qǐng)先調(diào)用 LoadTrieData 方法裝載字典樹");
      }
      //取詞的最大長度
      int maxLength = trie.MaxLength();
      //取詞的當(dāng)前長度
      int wordLength = maxLength;
      //分詞操作中,處于字符串中的當(dāng)前位置
      int position = 0;
      //分詞操作中,已經(jīng)處理的字符串總長度
      int segLength = 0;
      //用于嘗試分詞的取詞字符串
      string word = "";

      //用于儲(chǔ)存正向分詞的字符串?dāng)?shù)組
      List<string> segWords = new List<string>();
      //用于儲(chǔ)存逆向分詞的字符串?dāng)?shù)組
      List<string> segWordsReverse = new List<string>();

      //開始分詞,循環(huán)以下操作,直到全部完成
      while (segLength < inputStr.Length)
      {
        //如果剩余沒分詞的字符串長度<取詞的最大長度,則取詞長度等于剩余未分詞長度
        if ((inputStr.Length - segLength) < maxLength)
          wordLength = inputStr.Length - segLength;
        //否則,按最大長度處理
        else
          wordLength = maxLength;

        //從左到右 和 從右到左截取時(shí),起始位置不同
        //剛開始,截取位置是字符串兩頭,隨著不斷循環(huán)分詞,截取位置會(huì)不斷推進(jìn)
        if (leftToRight)
          position = segLength;
        else
          position = inputStr.Length - segLength - wordLength;

        //按照指定長度,從字符串截取一個(gè)詞
        word = inputStr.Substring(position, wordLength);


        //在字典中查找,是否存在這樣一個(gè)詞
        //如果不包含,就減少一個(gè)字符,再次在字典中查找
        //如此循環(huán),直到只剩下一個(gè)字為止
        while (!trie.Contains(word))
        {
          //如果最后一個(gè)字都沒有匹配,則把word設(shè)置為空,用來表示沒有匹配項(xiàng)(如果是分詞直接break)
          if (word.Length == 1)
          {
            word = null;
            break;
          }

          //把截取的字符串,最邊上的一個(gè)字去掉
          //從左到右 和 從右到左時(shí),截掉的字符的位置不同
          if (leftToRight)
            word = word.Substring(0, word.Length - 1);
          else
            word = word.Substring(1);
        }

        //將分出匹配上的詞,加入到分詞字符串?dāng)?shù)組中,正向和逆向不同
        if (word != null)
        {
          if (leftToRight)
            segWords.Add(word);
          else
            segWordsReverse.Add(word);
          //已經(jīng)完成分詞的字符串長度,要相應(yīng)增加
          segLength += word.Length;
        }
        else
        {
          //沒匹配上的則+1,丟掉一個(gè)字(如果是分詞 則不用判斷word是否為空,單個(gè)字也返回)
          segLength += 1;
        }
      }

      //如果是逆向分詞,對(duì)分詞結(jié)果反轉(zhuǎn)排序
      if (!leftToRight)
      {
        for (int i = segWordsReverse.Count - 1; i >= 0; i--)
        {
          //將反轉(zhuǎn)的結(jié)果,保存在正向分詞數(shù)組中 以便最后return 同一個(gè)變量segWords
          segWords.Add(segWordsReverse[i]);
        }
      }

      return segWords;
    }
  }

  這里使用了單例模式用來在項(xiàng)目中共用,在第一次裝入了字典樹后就可以在其他地方匹配錯(cuò)詞使用了。

  這個(gè)是結(jié)合我具體使用,簡化了些代碼,如果只是分詞的話就是分詞那個(gè)實(shí)現(xiàn)方法就行了。最后分享就到這里吧,如有不對(duì)之處,請(qǐng)加以指正。

到此這篇關(guān)于C#實(shí)現(xiàn)前向最大匹、字典樹(分詞、檢索)的示例代碼的文章就介紹到這了,更多相關(guān)C# 前向最大匹、字典樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Unity UI實(shí)現(xiàn)拖拽旋轉(zhuǎn)

    Unity UI實(shí)現(xiàn)拖拽旋轉(zhuǎn)

    這篇文章主要為大家詳細(xì)介紹了Unity UI實(shí)現(xiàn)拖拽旋轉(zhuǎn),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-06-06
  • C#學(xué)習(xí)筆記——基本語法

    C#學(xué)習(xí)筆記——基本語法

    本文給大家詳細(xì)介紹了C#的基本語法知識(shí)以及一些基礎(chǔ)知識(shí)的匯總,非常的簡單基礎(chǔ),有需要的小伙伴可以參考下
    2017-02-02
  • 淺談C#中的值類型和引用類型

    淺談C#中的值類型和引用類型

    在C#中值類型的變量直接存儲(chǔ)數(shù)據(jù),而引用類型的變量持有的是數(shù)據(jù)的引用,數(shù)據(jù)存儲(chǔ)在數(shù)據(jù)堆中。下面我們來簡單談?wù)凜#中的值類型和引用類型
    2016-06-06
  • Unity相機(jī)移動(dòng)之屏幕邊緣檢測

    Unity相機(jī)移動(dòng)之屏幕邊緣檢測

    這篇文章主要為大家詳細(xì)介紹了Unity相機(jī)移動(dòng)之屏幕邊緣檢測,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-02-02
  • 基于C#實(shí)現(xiàn)端口掃描器(單線程和多線程)

    基于C#實(shí)現(xiàn)端口掃描器(單線程和多線程)

    本文主要介紹了基于C#分別通過單線程和多線程實(shí)現(xiàn)端口掃描,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-12-12
  • C#遍歷刪除字符串中重復(fù)字符

    C#遍歷刪除字符串中重復(fù)字符

    這篇文章主要介紹了C#遍歷刪除字符串中重復(fù)字符的方法,涉及C#遍歷字符串的相關(guān)技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下
    2015-04-04
  • c#檢測文本文件編碼的方法

    c#檢測文本文件編碼的方法

    這篇文章主要介紹了c#檢測文本文件編碼的方法
    2016-03-03
  • 使用Spire.Barcode程序庫生成二維碼的實(shí)例解析

    使用Spire.Barcode程序庫生成二維碼的實(shí)例解析

    這篇文章主要介紹了使用Spire.Barcode程序庫生成二維碼的相關(guān)資料,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友可以參考下
    2016-12-12
  • c#泛型學(xué)習(xí)詳解 創(chuàng)建線性鏈表

    c#泛型學(xué)習(xí)詳解 創(chuàng)建線性鏈表

    Visual C# 2.0 的一個(gè)最受期待的(或許也是最讓人畏懼)的一個(gè)特性就是對(duì)于泛型的支持。這篇文章將告訴你泛型用來解決什么樣的問題,以及如何使用它們來提高你的代碼質(zhì)量,還有你不必恐懼泛型的原因
    2014-01-01
  • C#實(shí)現(xiàn)單例模式的幾種方法總結(jié)

    C#實(shí)現(xiàn)單例模式的幾種方法總結(jié)

    這篇文章主要介紹了C#實(shí)現(xiàn)單例模式的幾種方法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-01-01

最新評(píng)論