使用 C# 中的 C++ STL 向量进行快速字符串搜索

使用代码 

CSharpTest 项目  

CSharpTest 项目是一个控制台应用程序，演示了如何调用 C++ DLL 中公开的静态函数。 

第一步是填充数据结构。

//Populate the data structures
SuggestWin32.ST_CreateInit();
FileStream fs = new FileStream(@"..\..\dic.txt",
                               FileMode.Open, FileAccess.Read, FileShare.Read);
StreamReader sr = new StreamReader(fs, Encoding.Default);
int iCount = 0;
while (!sr.EndOfStream)
{
  string line = sr.ReadLine();
  if (line.Length > 0)
  {
    SuggestWin32.ST_insert(line, iCount++);
  }
}
sr.Close();
SuggestWin32.ST_write_to_file(@"..\..\spellchk.dat");
 

ST_CreateInit() 调用用于创建底层的 std::vector 容器（KVPCollection），同时还会初始化三元 DAG 节点的全局计数器。

ST_insert(line, iCount++) 将来自 dic.txt 文件的一行文本插入 KVPCollection 并向 DAGTree 结构添加一个节点。

插入所有数据后，将调用 ST_write_to_file 将两个数据结构进行二进制序列化到文件。两个文件使用相同的路径。您可以随意命名 DAGTree 序列化文件（此处为 spellchk.dat），KVPCollection 序列化文件命名为 dict.dat。这两个文件如果存在将被替换。KVPCollection 的 std:vector 成员在输出到 dict.dat 之前也会进行排序。  

要使用索引数据集，然后调用 ST_open_dict，如下所示。

IntPtr Dict = SuggestWin32.ST_open_dict(@"..\..\spellchk.dat");
 
if (Dict == null)
{
  Console.WriteLine("Missing or bad input file");
}
 

此调用会将数据从 spellchk.dat 和 dict.dat 反序列化到内存。这与 ST_write_to_file 的操作相反。如果 spellchk.dat 文件反序列化过程中出现任何错误，则返回 null。否则，将返回指向 DAGTree 根节点的 IntPtr 句柄。

如果序列化数据是最新的，您可以跳过写入直接调用 ST_open_dict。这可以节省应用程序启动的几秒钟时间。

此 C# 结构体用作引用参数来保存结果。请注意，结构体的内存是在托管端分配的，以便可以使用默认的结构体封送。

[StructLayout(LayoutKind.Sequential)]
public struct KVPIndex
{
  public int fid;
  public uint keySize;
  public string sKey;
}
 

使用 LayoutKind.Sequential 来确保字段的顺序与此结构体的 C++ 版本匹配。  

KVPIndex 类型创建如下。

KVPIndex kvp = new KVPIndex();
kvp.sKey = new String(' ', 50);
   

由于这是一个结构体，默认构造函数会将所有字段初始化为其 C# 默认值。

为 String 键成员 (sKey) 分配内存用于封送，分配了 50 个 字符的空间。这是通过使用创建具有 50 个重复空格的字符串的 String 构造函数重载来完成的。您选择使用的 char 实际上无关紧要。

默认封送会自动将 .NET String 类型转换为 C++ 端 的 const char* 缓冲区。 

在 do 循环内部，将测试每个用户提供的单词是否在数据集中匹配，并使用迭代器接口返回结果。

Console.Write("Enter a word to check: ");
word = Console.ReadLine();
if (word.Length > 0)
{
  //do a left-substring match on word and return the first instance
  SuggestWin32.ST_GetFirst(word, ref kvp);
  if (kvp.fid > -1)
  {
    for (; kvp.fid > -1; SuggestWin32.ST_GetNext(ref kvp))
    {
      Console.WriteLine("{0} fid:{1}", kvp.sKey, kvp.fid);
      kvp.sKey = new String(' ', 50);
    }
  }
  else //try to find words close to your spelling
  {
    int n;
    IntPtr KVPResults = SuggestWin32.ST_enum_suggestions(Dict, word, out n);
    if (n > 0)
    {
      for (SuggestWin32.ST_GetKVFirst(KVPResults, ref kvp); kvp.fid > -1; 
             SuggestWin32.ST_GetNext(ref kvp))
      {
        Console.WriteLine("{0} fid:{1}", kvp.sKey, kvp.fid);
        kvp.sKey = new String(' ', 50);
      }
    }
  }
}

ST_GetFirst 用于匹配 std::vector（包含 dict.dat 字符串）中以字符串参数开头的所有单词。匹配区分大小写。如果至少找到一个匹配项，则 kvp 对象将包含第一个匹配项。 否则，kvp.fid 将设置为 -1 以表示未找到匹配项。 

如果在第一次测试中未找到 word 的匹配项，则进行第二次测试以查找该单词的其他建议拼写。调用 ST_enum_suggestions 以创建包含建议拼写匹配项的 KVPIndex 对象 std::vector。将此数据结构的句柄 (KVPResults) 与匹配项的数量一起返回。

ST_GetNext 在下一个循环中调用，以获取 kvp 在匹配范围内的下一个迭代。然后进行 kvp.fid > -1 检查。这次，如果 kvp.fid == -1，则表示没有更多要返回的匹配项，并且 for 循环终止。 

如果在第一个测试中未找到匹配项，则进行第二次测试以查找该单词的其他建议拼写。调用 ST_enum_suggestions 以创建包含建议拼写匹配项的 KVPIndex 对象 std::vector。将此数据结构的句柄 (KVPResults) 与匹配项的数量一起返回。

然后，在 for 循环的初始化表达式中调用 ST_GetKVFirst 来开始迭代结果。ST_GetKVFirst 以 KVPResults 的句柄和 kvp 的引用作为参数。结果以与之前相同的方式返回到 kvp 中。

所有静态 extern 方法的原型都定义在 SuggestWin32 静态 C# 类中。

public static class SuggestWin32
{
    [DllImport("..\\..\\..\\Debug\\SpellSuggest.dll")]
    public static extern void ST_CreateInit();

    [DllImport("..\\..\\..\\Debug\\SpellSuggest.dll")]
    public static extern void ST_insert(string word, int index);

    [DllImport("..\\..\\..\\Debug\\SpellSuggest.dll")]
    public static extern bool ST_write_to_file(string path);

    [DllImport("..\\..\\..\\Debug\\SpellSuggest.dll")]
    public static extern IntPtr ST_open_dict(string filename);

    [DllImport("..\\..\\..\\Debug\\SpellSuggest.dll")]
    public static extern void ST_close_dict(IntPtr dict);

    [DllImport("..\\..\\..\\Debug\\SpellSuggest.dll")]
    public static extern IntPtr ST_enum_suggestions(IntPtr dict, string word, out int n);

    [DllImport("..\\..\\..\\Debug\\SpellSuggest.dll")]
    public static extern void ST_GetFirst(string cStr, [MarshalAs(UnmanagedType.Struct)] ref KVPIndex kvp);

    [DllImport("..\\..\\..\\Debug\\SpellSuggest.dll")]
    public static extern void ST_GetKVFirst(IntPtr KVPResults, [MarshalAs(UnmanagedType.Struct)]  ref KVPIndex kvp);

    [DllImport("..\\..\\..\\Debug\\SpellSuggest.dll")]
    public static extern void ST_GetNext([MarshalAs(UnmanagedType.Struct)] ref KVPIndex kvp);
 
} 

请注意，您只需要在 DLLImport 语句参数中提供 DLL 的路径。 还有其他可选设置，但本项目不需要它们。

对于本项目，静态方法原型所有参数都是 string、int、IntPtr 或 KVPIndex 类型。MarshalAs(UnmangedType.Struct) 是 C# 结构体的默认封送，但我添加了该语句只是为了清楚说明它对结构体参数做了什么。 

DllImport 可以设置为两种不同的调用约定：StdCall 或 Cdecl。 StdCall 是默认的（CE.NET 除外），如果导入的 C++ 函数接受可变数量的参数（例如 printf），则需要使用 Cdecl。

SpellSuggest 项目 

此项目的源代码包含两个文件夹：Header 和 Source。

Header 文件夹包含 CreateTree.h 和 spellchecker.h。 Source 文件夹包含 CreateTree.cpp 和 spellcheker.cpp。

CreateTree.h

此头文件包含三个函数原型导出。 

 extern "C" {
 
   __declspec(dllexport) void ST_CreateInit();
 
   //insert a string
   __declspec(dllexport) void ST_insert(const char* str, int index);
 
   //balance tree and write to file
   __declspec(dllexport) bool ST_write_to_file(const char* path);
} 

它还包含 KVPIndex 结构体的 C++ 非托管版本和 KVPCollection 结构体的 C++ 版本。

struct KVPIndex {
   int fid;
   size_t keySize;
   char *sKey;
};
 
struct KVPCollection
{
   std::vector<KVPIndex*> KVPVect;
 
   KVPCollection() { //constructor
      KVPVect.reserve(ST_MAX_ENTRIES);
   }
 
   ~KVPCollection() {
      vector<KVPIndex*>::iterator vit;
      for (vit=KVPVect.begin(); vit < KVPVect.end(); ++vit)
      {
         free((KVPIndex*)(*vit)->sKey);
         delete(*vit);
      }
   }
   //...
}

请注意，在 C++ 中，结构体与类相同，只是成员默认是公有的。

KVPCollection 的第一行创建了一个对象 KVPVect，它是 std::vector<KVPIndex*> 的一个实例。因此，KVPVect 的每个单元格都包含一个指向 KVPIndex 的指针。

构造函数预留了足够的单元格来容纳 ST_MAX_ENTRIES（300000）个指针。如果需要更多空间，vector 对象将重新分配一个更大的缓冲区，并将所有单元格内容（指针）复制到新缓冲区。 ST_CreateInit() 调用此构造函数来创建 KVPCollection 的实例；

析构函数释放为 sKey 和 KVPIndex 实例动态分配的内存。 

ST_insert 调用 KVPCollection 类中的 InsertCStr 方法。下面是该方法的实现。 

 //Insert the cStr with given index value into KVPVect if length > 0
 void InsertCStr(const char *cStr, int index)
 {
    KVPIndex* m_kvp;
    m_kvp = new KVPIndex();
    m_kvp->keySize = strlen(cStr);
 
    if (m_kvp->keySize > 0) {
       if (m_kvp->keySize >= KVPIndexC_sKey_Size) { 
          m_kvp->keySize = KVPIndexC_sKey_Size - 1; 
       }
       m_kvp->sKey = (char *)malloc(m_kvp->keySize + 1);
       strncpy(m_kvp->sKey, cStr, m_kvp->keySize);
       m_kvp->sKey[m_kvp->keySize] = '\0';
       m_kvp->fid = index;
       KVPVect.push_back(m_kvp);
    }
 }

为每个 sKey 指针分配最少内存，最多 50 个字符（包括 0 终止符）。给定的 index 参数被保存到 fid。

将相同的数据插入 DAGTree。有关 DAGTree 结构的更多信息，请参阅上方的三元 DAG Tree 链接。 

ST_write_to_file 调用 KVPCollection 类中的 Write 方法来创建 dict.dat 文件。 

 void Write(const char *fileName)
 {
    Sort();
    ofstream outFile(fileName, ios::out | ios::binary);
    char* out = (char*)malloc(sizeof(KVPIndexC));
    vector<KVPIndex*>::const_iterator vit;
    for (vit=KVPVect.begin(); vit < KVPVect.end(); ++vit)
    {
       //m_kvp = *vit; //for debug
       KVPIndex *kvpTemp = (KVPIndex*)*vit;
       memmove(out, (const void*)kvpTemp, 8);
       memmove(out+8, kvpTemp->sKey, kvpTemp->keySize + 1);
       outFile.write(out, kvpTemp->keySize + 9);
    }
    outFile.close();
 } 
 

对 KVPVect 进行排序，并使用 vector<KVPIndex*>::const_iterator 迭代 KVPVect 的内容，通过二进制写入方法将每个元素写入 outFile。

spellchecker.h 

此头文件包含在 CSharpTest 中导入的其余函数原型导出。 

extern "C" {
 __declspec(dllexport) size_t MAX_ENUM_WORDS();
}
 
// Open a dictionary, returns NULL in case of error
extern "C" {
 __declspec(dllexport) ST_FILE_NODE * ST_open_dict (const char * filename);
}
 
// Enumerate spelling suggestions (fuzzy matches)
extern "C" {
 __declspec(dllexport) std::vector<KVPIndex*> * ST_enum_suggestions (ST_FILE_NODE * dict, const char * word, int *n);
}
 
// Close the dictionary
extern "C" {
 __declspec(dllexport) void ST_close_dict (ST_FILE_NODE * dict);
}
 
extern "C" {
 __declspec(dllexport) void ST_GetFirst(const char *cStr, KVPIndex *kvpSt);
 __declspec(dllexport) void ST_GetKVFirst(std::vector<KVPIndex*> *KVPResults, KVPIndex *m_kvp);
}
 
extern "C" {
 __declspec(dllexport) void ST_GetNext(KVPIndex *kvpSt);
} 

ENumResults 结构体用于管理另一个 KVPVect，该 KVPVect 存储了在 ST_enum_suggestions 调用中生成的拼写建议列表。

struct ENumResults {
   std::vector<KVPIndex*> KVPVect;
 
   ~ENumResults() {
       vector<KVPIndex*>::iterator vit;
       for (vit=KVPVect.begin(); vit < KVPVect.end(); ++vit)
       {
          free((KVPIndex*)(*vit)->sKey);
          delete(*vit);
       }
   }
 
   void RemoveEntries() {
       vector<KVPIndex*>::iterator vit;
       for (vit=KVPVect.begin(); vit < KVPVect.end(); ++vit)
       {
          free((KVPIndex*)(*vit)->sKey);
          delete(*vit);
       }
       KVPVect.clear();
   }
};

析构函数与 RemoveEntries 类似，不同之处在于 RemoveEntries 释放所有元素占用的内存并清空 KVPVect，而不是删除 KVPVect 对象。

spellchecker.cpp  和 CreateTree.cpp

大多数用于 dllexport 的包装函数实现在 spellchecker.cpp 中。 

其中许多函数调用 KVPCollection 结构体中的方法，这些方法在 CreateTree.h 或 CreateTree.cpp 中实现。 

ST_GetFirst 调用 GetFirst 的一个重载，该重载实现在 CreateTree.cpp 中。 

一个 C 函数 comp 用于将 CompStr 与已排序的 std::vector 中的值范围进行比较。 

const char *CompStr; 

//Finds range of keys using left-substring match
bool comp(const KVPIndex *pred, const KVPIndex *range)
{
   if (strcmp(CompStr, range->sKey))
   {
      if (strcmp(CompStr, pred->sKey)) {
         return (strcmp(pred->sKey, range->sKey) < 0) ? true : false;
      }
      //CompStr == pred->sKey
      if (range->keySize <= pred->keySize) { 
         return (strcmp(pred->sKey, range->sKey) < 0) ? true : false;
      }
      return (strncmp(pred->sKey, range->sKey, pred->keySize) < 0) ? true : false;
   }
   else //CompStr == range->sKey
   {
      if (pred->keySize <= range->keySize) { 
         return (strcmp(pred->sKey, range->sKey) < 0) ? true : false;
      }
      return (strncmp(pred->sKey, range->sKey, range->keySize) < 0) ? true : false;
   }
}

pred 和 range 实际上是可互换的，因此 CompStr 用于保存搜索字符串，以便正确地将 CompStr 作为子字符串左匹配 sKey 向量元素。如果 CompStr 长度小于向量键项，则仅应比较输入键的大小。范围键中超出输入键长度的右侧部分可以忽略。此函数花了一些调试时间才使其正确处理左匹配。 

这是 GetFirst 的实现。

void KVPCollection::GetFirst(const char *cStr, KVPIndex *m_kvp, bool (*compFunc)(const KVPIndex *, const KVPIndex *))
{
   m_kvp->fid = -1;
   int len = strlen(cStr);
   if (len > 0) {
      CompStr = cStr; //save to use in comp function
      KVPIndex* kvp;
      kvp = new KVPIndex(); //create temparary search term for predicate
      kvp->keySize = len;
      if (len >= KVPIndexC_sKey_Size) { 
         kvp->keySize = KVPIndexC_sKey_Size - 1;
      }
      kvp->sKey = (char *)malloc(kvp->keySize + 1);
      strncpy(kvp->sKey, cStr, kvp->keySize);
      kvp->sKey[kvp->keySize] = '\0';
      lowBound = lower_bound(KVPVect.begin(), KVPVect.end(), kvp, compFunc);
      upBound = upper_bound(KVPVect.begin(), KVPVect.end(), kvp, compFunc);
 
      free(kvp->sKey);
      delete kvp; //delete search term;

      if (lowBound != upBound)
      {
         m_kvp->fid = ((KVPIndex*)*lowBound)->fid;
         m_kvp->keySize = ((KVPIndex*)*lowBound)->keySize;
         strcpy(m_kvp->sKey, ((KVPIndex*)*lowBound)->sKey);
      }
      kvpIter = lowBound;
   }
}

搜索项必须是 KVPIndex* 类型才能匹配 std::vector 的元素类型。因此，创建 kvp 并将其设置为给定 cStr 参数的值。 

使用 std::lower_bound 和 std::upper_bound 方法找到 vector<KVPIndex*>::iterator lowBound 和 upBound。 

然后，在 m_kvp 引用参数中设置成员字段，使其包含 lowBound 迭代器的内容。 

另一个 GetFirst 重载（在 CreateTree.h 中实现）要简单得多。它仅获取 ST_enum_suggestions 返回的结果向量，并将第一个元素指针保存到 kvpIter，将 end() 指针保存到 upBound。

调用 GetNext（在 CreateTree.h 中实现）以获取下一个元素，直到达到 upBound。一旦达到 upBound，m_kvp 引用参数的最终 m_kvp->fid 值将为 -1。

   void GetNext(KVPIndex *m_kvp)
   {
      m_kvp->fid = -1;
      if (++kvpIter != upBound) {
         //return (KVPIndex*)(*kvpIter);
         m_kvp->fid = ((KVPIndex*)*kvpIter)->fid;
         m_kvp->keySize = ((KVPIndex*)*kvpIter)->keySize;
         strcpy(m_kvp->sKey, ((KVPIndex*)*kvpIter)->sKey);
      }
   }

请注意，m_kvp->sKey 的内存是在托管代码中分配的。这消除了 C# 中将非托管内存缓冲区封送回托管内存所需的大量额外工作。 

ST_enum_suggestions 和 fuzzy_match

我主要在这些函数周围对原始三元 DAG 算法进行了修改。 

// Enumerate spelling suggestions (fuzzy matches)
std::vector<KVPIndex*> * ST_enum_suggestions (ST_FILE_NODE * dict, const char * word, int *n)
{
   static ST_ENUMINFO enuminfo; //everything initialized to 0 by default
   if (enuminfo.nresults > 0) {
      enuminfo.results.RemoveEntries();
      enuminfo.nresults = 0;
   }
   else
   {
      enuminfo.results.KVPVect.reserve(500);
	   enuminfo.dict = dict;
   }
   fuzzy_match(dict + 1, word, enuminfo.result, &enuminfo);
   *n = enuminfo.nresults;
   return &(enuminfo.results.KVPVect);
}

我在第一行添加了 static 关键字。这会导致变量在堆上仅分配一次，而不是自动分配到堆栈。所有成员也默认初始化为 0。这样我就可以重用该对象并清除其中的条目。 

我还删除了 (*enumproc) 函数参数，并添加了 *n 来保存结果的数量，以便调用者可以使用。 

该函数还被更改为返回指向 KPVect 结果向量的指针。然后，此指针从 C# 接口在 ST_GetKVFirst 函数中传递回来，以开始迭代建议拼写结果集。 

fuzzy_match 中唯一改变的是将 report_suggestion 函数替换为 add_suggestion。一旦我有了结果对象向量，我就可以在 C# 中收集它。我不想传递一个函数来在 C++ 中处理每个结果。 

static void add_suggestion(ST_ENUMINFO * enuminfo) {
 
   KVPIndex *kvp = new KVPIndex();
   kvp->sKey = (char *)malloc(50);
    //find range that matches suggested spelling
   for (s_kvpList->GetFirst(enuminfo->result, kvp, compExact); kvp->fid > -1; s_kvpList->GetNext(kvp))
   {
      enuminfo->results.KVPVect.push_back(kvp);
      ++(enuminfo->nresults);
      kvp = new KVPIndex();
      kvp->sKey = (char *)malloc(50);
   }
}

请注意，我需要分配 50 字节来保存 char 缓冲区，这样一切都可以与 GetFirst 参数来自 C# 时一样正常工作。 

如果存在重复匹配项，我仍然希望返回所有匹配项，因为它们在我的应用程序源数据中具有不同的 fid 值。为了允许重复的字符串结果，我仍然像进行左匹配一样迭代建议拼写的每个匹配项。只不过这次，比较函数是 compExact 而不是 comp。 

这是 CreateTree.cpp 中的 compExact 实现。 

//Finds range of keys using full matach
bool compExact(const KVPIndex *pred, const KVPIndex *range)
{
  return (strcmp(pred->sKey, range->sKey) < 0) ? true : false;
} 

这比 comp 函数的实现要简单得多，因为它只比较完整的字符串匹配项，而不是左子字符串匹配项。 

结论 

历史