DeltaScope

• 下载源代码 - 52.89 KB
• 下载二进制文件 - 39.93 KB

引言

这是Code Project的“精简高效”竞赛的候选作品，旨在编写一个高效的文本delta工具。

我在度假时查看邮件，发现了一封Code Project每日邮件，提醒我关于LCS竞赛的事情。我多年来一直喜欢阅读Code Project的文章，但直到现在我才有机会贡献。

当我刚开始学习C#时，我决定编写一个diff程序，以便真正学习这门语言。我称这个程序为DeltaScope。它最初只是一个简单的基于控制台的diff工具，经过了许多次迭代。当我最终停止工作时，我拥有一个可重用的delta引擎，带有GDI+前端控件。

不幸的是，我从2005年起就再也没有接触过这段代码。感谢我的未婚夫非常理解我的“编码时间”，我得以抽出时间编写这篇文章，并将代码更新到C# 3.0规范。

最长公共子序列

许多参赛作品都对LCS算法进行了出色的解释。当我编写DeltaScope时，我广泛参考了这篇论文。http://www.ics.uci.edu/~eppstein/161/960229.html[^]

我发现理解LCS算法的最佳方法是这样思考：
delta操作的输出是将文件1转换为文件2的一系列指令。

关注点

该系统的核心是DeltaEngine类。DeltaScope应用程序将引擎包装在DeltaScopeEngine类中。

public class DeltaScopeEngine 
{
        public bool IgnoreCase { get; set; }
        public bool IgnoreTabs { get; set; }

        public TimeSpan ElapsedTime { get; private set; }
        public long PeakMemoryUsage { get; private set; }

        public List<DeltaBlock> Compare(string tsLeftFile, string tsRightFile)
        {
            var process = Process.GetCurrentProcess();
            process.Refresh();
            var peakWorkingSet64 = process.PeakWorkingSet64;

            var timer = DateTime.Now;
            var deltaEngine = new DeltaEngine();
            var result = deltaEngine.GetDifferences(RipFile(tsLeftFile),
                RipFile(tsRightFile), hashSideDelegate);
            ElapsedTime = DateTime.Now - timer;
            PeakMemoryUsage = process.PeakWorkingSet64 - peakWorkingSet64;
            
            return result;
        }
        private static string RipFile(string tsFileName)
        {
            ...
        }
        private List<DeltaString> hashSideDelegate(string sideValues)
        {
            const string blockLineTerminator = @"\r\n";
            var values = new List<string>(Regex.Split(sideValues, blockLineTerminator));
            var results = new List<DeltaString>();

            for (var lnCnt = 0; lnCnt < values.Count; lnCnt++)
            {
                var lnHashCode = _GenerateHashFromString(values[lnCnt]);
                if (lnHashCode >= 0)
                    results.Add(new DeltaString(values[lnCnt], lnHashCode));
            }
            return results;
        }
        private int _GenerateHashFromString(string tsLine)
        {
            var lnHash = 0;
            var lnRealPtr = 0;
            
            // Handle the upper casing issue...
            var lcaLine = IgnoreCase ? 
                tsLine.ToUpper().ToCharArray() : tsLine.ToCharArray();

            // hash_string(ABCW) = 65*1 + 66*2 + 67*3 + 87*4
            var lnMaxLength = lcaLine.Length;
            for (var lnCnt = 0; lnCnt < lnMaxLength; lnCnt++)
            {
                // Handle the white space characters...
                if (lcaLine[lnCnt] == '\t' && IgnoreTabs)
                    continue;

                lnRealPtr++;
                lnHash += ((byte)lcaLine[lnCnt] * lnRealPtr);
            }

            // return the hash value...
            return (lnHash);
        }
}

hashAlgorithm委托允许开发人员控制如何将每个字符串解析为DeltaStrings列表。在这个简单的例子中，我们可以选择使差异区分大小写或不区分大小写，并且可以选择忽略制表符字符。

计时和内存消耗

平均运行时间为13毫秒。我的计时不包括任何屏幕渲染。至于内存消耗，我总是得到0内存使用。这意味着我要么没有正确使用process.PeakWorkingSet64，要么我的代码是神奇的。;)

未来方向

许多diff工具允许用户将2个文件合并成1个新文件。有了DeltaEngine生成的delta块列表，应该可以允许用户构建一个新文件。这需要某种块选择能力，以及可能需要文本编辑。不幸的是，当前的GDI+控件仅用于显示。

当我最初编写这个程序时，GDI+还是一项相当新的技术，而WPF尚未存在。我认为下一步的好方法是使用WPF作为显示技术。使用WPF，可以重写旋涡块控件以包含编辑功能。