algorithm - 如何检测文件是否已更改？

Question

我正在尝试编写一个用于处理大文件的文字处理器程序。现在，每当用户关闭文件时，如果文件已被修改，我会提示他们“是否要保存文件”。

我正在使用每当用户执行任何写操作时设置的脏位来实现这一点。

但是，这有一个限制，即当文件实际上并不脏时，它会被视为脏文件。例如，如果用户键入一个字符并将其删除，则该文件没有更改。但是我的“脏位”实现认为它已经改变了。

就速度而言，检测文件是否真的发生变化的最佳方法是什么？

对整个文件进行完整的逐位比较太慢了。（比较文件哈希也太慢了，因为需要处理整个文件以计算哈希。在比较值之前先进行长度比较在长度不同时有效，但在长度不同时失败，就像在我的示例中一样以上。）

Answer 1

由于这是一个文字处理器程序，它也可以有一个动作历史。您可以维护 2 个堆栈，一个用于历史操作（已合并的更改），另一个用于将来的操作（已应用但现在已以线性方式恢复的更改）。

例如，按顺序输入的每个字符都可以是动作堆栈中的一个项目，将其删除可能相当于将该动作从历史项目堆栈弹出到未来动作堆栈（以防您需要重做动作）。

现在，只要历史操作的堆栈不为空，您就会提示用户在关闭时关闭文件。

为简单起见，您可以拥有有限数量的历史记录项（例如最后 100 个操作）。然后，由于每个用户操作都在对文档进行每次添加/减去操作，因此几乎没有任何延迟，并且确定堆栈是否为空是一个 O(1) 操作。