如何測量除計算距離外的2個字符串的相似度

Question

我正在創建一個程序，用於檢查單詞是否爲簡化字（txt，msg等），如果它被簡化，它會找到正確的拼寫，如txt = text， MSG =消息。 Iam在c＃中使用NHunspell建議方法，其中提出了所有可能的結果。

問題是如果我輸入「txt」的結果是文本，tat，tot等，我不知道如何選擇正確的單詞。我用Levenshtein距離（C# - Compare String Similarity），但結果還是結果1

輸入：TXT 結果：文本= 1，EXT = 1個針鋒相對= 1

你能幫我如何獲得意義或正確拼寫簡體字？ 例子：味精

Answer 1

不是一個完整的解決方案，只是希望有益的建議......

在我看來，人是不太可能使用，只要是作爲正確的單詞簡化，這樣你至少可以濾除長度爲< =輸入長度的所有結果。

Answer 2

我與您的樣本數據來測試你的輸入，只有text擁有25的距離，而其他有33的距離這裏是我的代碼：

string input = "TXT"; 
string[] words = new[]{"text","tat","tot"}; 
var levenshtein = new Levenshtein(); 
const int maxDistance = 30; 

var distanceGroups = words 
     .Select(w => new 
     { 
      Word = w, 
      Distance = levenshtein.iLD(w.ToUpperInvariant(), input) 
     }) 
     .Where(x => x.Distance <= maxDistance) 
     .GroupBy(x => x.Distance) 
     .OrderBy(g => g.Key) 
     .ToList(); 
foreach (var topCandidate in distanceGroups.First()) 
    Console.WriteLine("Word:{0} Distance:{1}", topCandidate.Word, topCandidate.Distance); 

這裏是萊文斯坦類：

public class Levenshtein 
{ 
    ///***************************** 
    /// Compute Levenshtein distance 
    /// Memory efficient version 
    ///***************************** 
    public int iLD(String sRow, String sCol) 
    { 
     int RowLen = sRow.Length; // length of sRow 
     int ColLen = sCol.Length; // length of sCol 
     int RowIdx;    // iterates through sRow 
     int ColIdx;    // iterates through sCol 
     char Row_i;    // ith character of sRow 
     char Col_j;    // jth character of sCol 
     int cost;     // cost 

     /// Test string length 
     if (Math.Max(sRow.Length, sCol.Length) > Math.Pow(2, 31)) 
      throw (new Exception("\nMaximum string length in Levenshtein.iLD is " + Math.Pow(2, 31) + ".\nYours is " + Math.Max(sRow.Length, sCol.Length) + ".")); 

     // Step 1 

     if (RowLen == 0) 
     { 
      return ColLen; 
     } 

     if (ColLen == 0) 
     { 
      return RowLen; 
     } 

     /// Create the two vectors 
     int[] v0 = new int[RowLen + 1]; 
     int[] v1 = new int[RowLen + 1]; 
     int[] vTmp; 



     /// Step 2 
     /// Initialize the first vector 
     for (RowIdx = 1; RowIdx <= RowLen; RowIdx++) 
     { 
      v0[RowIdx] = RowIdx; 
     } 

     // Step 3 

     /// Fore each column 
     for (ColIdx = 1; ColIdx <= ColLen; ColIdx++) 
     { 
      /// Set the 0'th element to the column number 
      v1[0] = ColIdx; 

      Col_j = sCol[ColIdx - 1]; 


      // Step 4 

      /// Fore each row 
      for (RowIdx = 1; RowIdx <= RowLen; RowIdx++) 
      { 
       Row_i = sRow[RowIdx - 1]; 


       // Step 5 

       if (Row_i == Col_j) 
       { 
        cost = 0; 
       } 
       else 
       { 
        cost = 1; 
       } 

       // Step 6 

       /// Find minimum 
       int m_min = v0[RowIdx] + 1; 
       int b = v1[RowIdx - 1] + 1; 
       int c = v0[RowIdx - 1] + cost; 

       if (b < m_min) 
       { 
        m_min = b; 
       } 
       if (c < m_min) 
       { 
        m_min = c; 
       } 

       v1[RowIdx] = m_min; 
      } 

      /// Swap the vectors 
      vTmp = v0; 
      v0 = v1; 
      v1 = vTmp; 

     } 

     // Step 7 

     /// Value between 0 - 100 
     /// 0==perfect match 100==totaly different 
     /// 
     /// The vectors where swaped one last time at the end of the last loop, 
     /// that is why the result is now in v0 rather than in v1 
     //System.Console.WriteLine("iDist=" + v0[RowLen]); 
     int max = System.Math.Max(RowLen, ColLen); 
     return ((100 * v0[RowLen])/max); 
    } 


    ///***************************** 
    /// Compute the min 
    ///***************************** 

    private int Minimum(int a, int b, int c) 
    { 
     int mi = a; 

     if (b < mi) 
     { 
      mi = b; 
     } 
     if (c < mi) 
     { 
      mi = c; 
     } 

     return mi; 
    } 

    ///***************************** 
    /// Compute Levenshtein distance   
    ///***************************** 
    public int LD(String sNew, String sOld) 
    { 
     int[,] matrix;    // matrix 
     int sNewLen = sNew.Length; // length of sNew 
     int sOldLen = sOld.Length; // length of sOld 
     int sNewIdx; // iterates through sNew 
     int sOldIdx; // iterates through sOld 
     char sNew_i; // ith character of sNew 
     char sOld_j; // jth character of sOld 
     int cost; // cost 

     /// Test string length 
     if (Math.Max(sNew.Length, sOld.Length) > Math.Pow(2, 31)) 
      throw (new Exception("\nMaximum string length in Levenshtein.LD is " + Math.Pow(2, 31) + ".\nYours is " + Math.Max(sNew.Length, sOld.Length) + ".")); 

     // Step 1 

     if (sNewLen == 0) 
     { 
      return sOldLen; 
     } 

     if (sOldLen == 0) 
     { 
      return sNewLen; 
     } 

     matrix = new int[sNewLen + 1, sOldLen + 1]; 

     // Step 2 

     for (sNewIdx = 0; sNewIdx <= sNewLen; sNewIdx++) 
     { 
      matrix[sNewIdx, 0] = sNewIdx; 
     } 

     for (sOldIdx = 0; sOldIdx <= sOldLen; sOldIdx++) 
     { 
      matrix[0, sOldIdx] = sOldIdx; 
     } 

     // Step 3 

     for (sNewIdx = 1; sNewIdx <= sNewLen; sNewIdx++) 
     { 
      sNew_i = sNew[sNewIdx - 1]; 

      // Step 4 

      for (sOldIdx = 1; sOldIdx <= sOldLen; sOldIdx++) 
      { 
       sOld_j = sOld[sOldIdx - 1]; 

       // Step 5 

       if (sNew_i == sOld_j) 
       { 
        cost = 0; 
       } 
       else 
       { 
        cost = 1; 
       } 

       // Step 6 

       matrix[sNewIdx, sOldIdx] = Minimum(matrix[sNewIdx - 1, sOldIdx] + 1, matrix[sNewIdx, sOldIdx - 1] + 1, matrix[sNewIdx - 1, sOldIdx - 1] + cost); 

      } 
     } 

     // Step 7 

     /// Value between 0 - 100 
     /// 0==perfect match 100==totaly different 
     //System.Console.WriteLine("Dist=" + matrix[sNewLen, sOldLen]); 
     int max = System.Math.Max(sNewLen, sOldLen); 
     return (100 * matrix[sNewLen, sOldLen])/max; 
    } 
} 

Answer 3

擴展我的評論，你可以使用正則表達式來搜索輸入的'擴展'的結果。事情是這樣的：

private int stringSimilarity(string input, string result) 
{ 
    string regexPattern = "" 
    foreach (char c in input) 
     regexPattern += input + ".*" 

    Match match = Regex.Match(result, regexPattern, 
    RegexOptions.IgnoreCase); 

    if (match.Success) 
     return 1; 
    else 
     return 0; 
} 

忽略1和0 - 我不知道該如何估價相似的作品。

Answer 4

您確實需要實現存在於SQL中的SOUNDEX例程。我已經做了，在下面的代碼：

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace Soundex 
{ 
    class Program 
    { 
     static char[] ignoreChars = new char[] { 'a', 'e', 'h', 'i', 'o', 'u', 'w', 'y' }; 
     static Dictionary<char, int> charVals = new Dictionary<char, int>() 
     { 
      {'b',1}, 
      {'f',1}, 
      {'p',1}, 
      {'v',1}, 
      {'c',2}, 
      {'g',2}, 
      {'j',2}, 
      {'k',2}, 
      {'q',2}, 
      {'s',2}, 
      {'x',2}, 
      {'z',2}, 
      {'d',3}, 
      {'t',3}, 
      {'l',4}, 
      {'m',5}, 
      {'n',5}, 
      {'r',6} 
     }; 

     static void Main(string[] args) 
     { 
      Console.WriteLine(Soundex("txt")); 
      Console.WriteLine(Soundex("text")); 
      Console.WriteLine(Soundex("ext")); 
      Console.WriteLine(Soundex("tit")); 
      Console.WriteLine(Soundex("Cammmppppbbbeeelll")); 
     } 

     static string Soundex(string s) 
     { 
      s = s.ToLower(); 
      StringBuilder sb = new StringBuilder(); 
      sb.Append(s.First()); 
      foreach (var c in s.Substring(1)) 
      { 
       if (ignoreChars.Contains(c)) { continue; } 

       // if the previous character yields the same integer then skip it 
       if ((int)char.GetNumericValue(sb[sb.Length - 1]) == charVals[c]) { continue; } 

       sb.Append(charVals[c]); 
      } 
      return string.Join("", sb.ToString().Take(4)).PadRight(4, '0'); 
     } 
    } 
} 

看到，隨着這個代碼，唯一的賽出局的你給的例子是text。運行控制檯應用程序，你會看到輸出（即txt將匹配text）。

Answer 5

我認爲像word這樣的程序用於糾正拼寫的一種方法是使用NLP（自然語言處理）技術來獲取在拼寫錯誤環境中使用的名詞/形容詞的順序。然後將其與已知句子進行比較他們可以估計70％的機會，拼寫錯誤是一個名詞，並使用該信息來過濾糾正的拼寫。

SharpNLP看起來像一個很好的圖書館，但我還沒有機會擺弄它呢。爲了建立一個已知的句子結構庫BTW，我們將我們的算法應用到公共領域的書籍中。

檢出sams simMetrics library我在SO上找到了（download here,docs here），用於加載更多Levenshtein距離算法的選項。