c++ - 字符串存储优化

Question

我正在寻找一些 C++ 库，它可以通过在内存中仅存储一次相似(不完全)的字符串来帮助优化内存使用。它不是 FlyWeight 或字符串实习，它只能存储一次精确的对象/字符串。该库应该能够分析和理解，例如，两个不同长度的特定字符串具有相同的前 100 个字符，该子字符串应该只存储一次。
示例 1:

std::string str1 = "http://www.contoso.com/some/path/app.aspx?ch=test1"<br/>
std::string str2 = "http://www.contoso.com/some/path/app.aspx?ch=test2"<br/>

在这种情况下，很明显这两个字符串的唯一区别是最后一个字符，所以如果我们只保存一个“http://www.contoso.com/some/path/app.aspx?ch=test”拷贝，然后再保存两个额外的字符串“1”，这将大大节省内存"和 "2"
示例 2:

std::string str1 = "http://www.contoso.com/some/path/app.aspx?ch1=test1"<br/>
std::string str2 = "http://www.contoso.com/some/path/app.aspx?ch2=test2"<br/>

当有多个相同的子字符串时，情况会更复杂:“http://www.contoso.com/some/path/app.aspx?ch”的一个拷贝，然后是两个字符串“1”和“2”，一个“=test”的拷贝，因为我们已经有了字符串“1” "和 "2"存储我们不需要任何额外的字符串。
那么，有这样的图书馆吗？有什么可以帮助相对快速地开发这样的库吗？字符串是不可变的，因此无需担心为线程安全更新索引或锁

Answer 1

1. 如果字符串具有公共(public)前缀，解决方案可能是 - 使用基数树(也称为 trie)( http://en.wikipedia.org/wiki/Radix_tree ) 来表示字符串。所以你只能存储指向树叶的指针。并通过成长到树根获得整个字符串。

   hello world
   hello winter
   hell
   
          [2]
          /
   h-e-l-l-o-' '-w-o-r-l-d-[0]
                  \
                   i-n-t-e-r-[1]
   

2. 这是另一种解决方案:http://en.wikipedia.org/wiki/Rope_(data_structure)

   libstdc++ 实现:https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.3/a00223.html

   SGI 文档:http://www.sgi.com/tech/stl/Rope.html

   但我认为您需要为 rope 构造字符串才能正常工作。可能找到每个新字符串与前一个字符串的最长公共(public)前缀和后缀，然后将新字符串表示为前一个字符串前缀、uniq 部分和前一个字符串后缀的串联。