替换字符串中的重复字符

Question

使用C#是否可以查找和替换字符串中的任何重复字符？我正在尝试减小从jpeg图像转换而来的base64字符串的大小。我注意到base64字符串包含许多重复的字符，例如：6qdQAUUxJA7uuCGQ8g/wA6fQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRRQAUUUUAFFFFABRRR等等。如果有一种方法可以使用以下内容删除重复的字符，那么它将会更小：[QAUUUUAFFFFABRRR, 18]。这是格式为[REPEATED-CHARACTERS，NUMBER-OF-TIMES]的格式。这样做可能吗？感谢您的帮助 :)

- Joey Morani

---

当然，但是您将不得不更改使用BASE64编码的任何电子邮件客户端（我想这就是问题所在）的代码。 - Parallelis

你可以尝试压缩它。字典的开销可能不值得，但基本上这就是它所做的。但如果你打算用ASCII传输结果，那么你可能需要调整算法以使用字符而不是位。 - lc.

由于JPEG图像已经在内部进行了压缩，因此您的压缩策略将不会产生任何结果。查看文件中后面的字节，就可以理解我的意思了。 - usr

一个简单的做法是使用 HashMap，当它在映射中遇到相同的值时，将增加该值。它将给出 O(n) 的复杂度。 - Dhruvenkumar Shah

Answer 1

您可以找到具有最大重复次数的最长字符串。

int mx = -1;
string str = null;
for (int i = 0; i < str.Length; i++) for (int j = i + 1; j < str.Length; j++)
{
string sub = str.Substring(i, j - i);
int tmp = countAll(str, sub); // write countAll() yourself
if (tmp > mx) { mx = tmp; str = sub; }
}

或者更好的方法是使用一个“字典”。

Dictionary<char, int> rep = new Dictionary<char, int>();
for (int i = 0; i < str.Length; i++)
  if (rep.ContainsKey(str[i])) rep[str[i]]++;
  else rep.Add(str[i], 1);

然后，您将得到每个字符及其出现次数的关联：

string total = "";
foreach (var item in rep) total += item.Key;

添加:

如果你真的想要找到最长重复子串，那么你应该使用动态规划来解决这个问题。

- user586399

Answer 2

你需要创建一个搜索和替换功能。这取决于重复字符串是否具有恒定的长度。在你的例子中，重复字符串长度为16个字符，因此你可以编写一个路由函数，获取前16个字符，将它们与下一个16个字符进行比较，直到找到一个不同的字符串。然后用你的语法来代表它们。

如果重复字符串的长度是可变的，那么就更加复杂了。你需要从一个短字符串开始，不断增长，并将其与相同长度的下一组字符进行比较，如果它们重复，则检查下一组字符，以此类推。但这可能会有所偏差。

搜索压缩算法，因为许多压缩算法都使用类似的原理。

- Dominique

Answer 3

你基本上是在尝试设计自己的无损压缩算法 - 像zip这样的算法正是在做你所要求的事情，只不过它们是针对字节而不是字符串中的字符进行操作。

流行的压缩算法几乎肯定比你能够在合理的时间内设计和实现的算法更有效。首先，它们可能会看到由于字节对齐问题在base64字符串中不明显的模式。

那么为什么不直接使用其中之一来压缩二进制数据，在进行base64编码之前呢？

- Sean U