导航：
论坛 ->
DELPHI技术 斑竹:liumazi,sephil
作者：
(haonan) ▲△△△△ -
注册会员
2015-8-7 14:34:26
标题： 字符串比较的方法 浏览:822
加入我的收藏楼主： 想要找出两个字条串有几个字符不同,有没有比较快的方法
我用一个字符一个字符的比较速度特别慢
----------------------------------------------
-
作者：
(孤独骑士) ▲▲▲▲▲ -
盒子活跃会员
2015-8-7 15:52:17
1楼： 试试hash，而且可以部分比较速度更快
----------------------------------------------
-
作者：
(jingtong) ▲▲▲△△ -
注册会员
2015-8-7 17:49:49
2楼： 搜索"编辑距离"算法
----------------------------------------------
18114532@qq.com
作者：
( 旺财) ▲▲▲▲△ -
普通会员
2015-8-7 19:21:37
3楼：
http://wiki.freepascal.org/Levenshtein_distance----------------------------------------------
免费的FTP
http://delphi.icm.edu.pl/ftp/
http://delphi-z.ru作者：
(sanlang) ▲▲▲△△ -
注册会员
2015-8-7 22:14:17
4楼： simhash
----------------------------------------------
-
作者：
(FengLinYuShu) ▲▲▲▲▲ -
盒子活跃会员
2015-8-8 23:35:10
5楼： 学习! 也正需要这个
有没有算出差别是哪几个具体字符串的函数?
----------------------------------------------
-
直接用Delphi开发网络应用程序
http;//www.web0000.com
作者：
(cafetoi) ▲▲▲△△ -
注册会员
2015-8-9 18:59:07
6楼： 這裡有一個
http://flocke.vssd.de/prog/code/pascal/pasdiff/----------------------------------------------
-
作者：
(FengLinYuShu) ▲▲▲▲▲ -
盒子活跃会员
2015-8-16 9:55:59
7楼： 看了一下, 用起来感觉还是不爽! 而且内存占用超大.
看一个C#的教程做了一个小内存版的
function GetFastLevDist(sRow,sCol:string):Integer;
var
I,J,M,N : Integer;
v0,v1 : TIntegerDynArray;
vTmp : TIntegerDynArray;
RowLen : Integer; // length of sRow
ColLen : Integer; // length of sCol
RowIdx : Integer; // iterates through sRow
ColIdx : Integer; // iterates through sCol
Row_i : char; // ith character of sRow
Col_j : char; // jth character of sCol
cost : Integer; // cost
m_min : Integer;
b,c : Integer;
maxlen : Integer;
begin
{
1 设置n为字符串s的长度。(“GUMBO”)
设置m为字符串t的长度。(“GAMBOL”)
如果n等于0，返回m并退出。
如果m等于0，返回n并退出。
构造两个向量v0[m+1] 和v1[m+1]，串联0..m之间所有的元素。
2 初始化 v0 to 0..m。
3 检查 s (i from 1 to n) 中的每个字符。
4 检查 t (j from 1 to m) 中的每个字符
5 如果 s[i] 等于 t[j]，则编辑代价为 0；
如果 s[i] 不等于 t[j]，则编辑代价为1。
6 设置单元v1[j]为下面的最小值之一：
a、紧邻该单元上方+1：v1[j-1] + 1
b、紧邻该单元左侧+1：v0[j] + 1
c、该单元对角线上方和左侧+cost：v0[j-1] + cost
7 在完成迭代 (3, 4, 5, 6) 之后，v1[m]便是编辑距离的值。
}
{
N := Length(S);
M := Length(T);
//
SetLength(v0,M+1);
SetLength(v1,M+1);
}
//
RowLen := Length(sRow); // length of sRow
ColLen := Length(sCol); // length of sCol
/// Test string length
if (Max(RowLen, ColLen) > IntPower(2, 31)) then
begin
ShowMessage('字符串太长');//throw (new Exception("\nMaximum string length in Levenshtein.iLD is " + Math.Pow(2, 31) + ".\nYours is " + Math.Max(sRow.Length, sCol.Length) + "."));
end;
// Step 1
if (RowLen = 0) then
begin
Result := ColLen;
Exit;
end;
if (ColLen = 0) then
begin
result := RowLen;
Exit;
end;
/// Create the two vectors
SetLength(v0,RowLen + 1);
SetLength(v1,RowLen + 1);
/// Step 2
/// Initialize the first vector
for RowIdx := 1 to RowLen do
begin
v0[RowIdx] := RowIdx;
end;
// Step 3
/// Fore each column
for ColIdx := 1 to ColLen do
begin
/// Set the 0'th element to the column number
v1[0] := ColIdx;
Col_j := sCol[ColIdx ];
// Step 4
/// Fore each row
for RowIdx := 1 to RowLen do
begin
Row_i := sRow[RowIdx];
// Step 5
if (Row_i = Col_j)then
begin
cost := 0;
end
else
begin
cost := 1;
end;
// Step 6
/// Find minimum
m_min := v0[RowIdx] + 1;
b := v1[RowIdx - 1] + 1;
c := v0[RowIdx - 1] + cost;
if (b < m_min) then
begin
m_min := b;
end;
if (c < m_min) then
begin
m_min := c;
end;
v1[RowIdx] := m_min;
end;
/// Swap the vectors
//vTmp := v0;
//v0 := v1;
//v1 := vTmp;
DWSetArray(vTmp,v0);
DWSetArray(v0,v1);
DWSetArray(v1,vTmp);
end;
// Step 7
/// Value between 0 - 100
/// 0==perfect match 100==totaly different
///
/// The vectors where swaped one last time at the end of the last loop,
/// that is why the result is now in v0 rather than in v1
//System.Console.WriteLine("iDist=" + v0[RowLen]);
maxlen := Max(RowLen, ColLen);
Result := v0[RowLen];//Round ((100 * v0[RowLen]) / maxlen);//
//
//计算的值与原算法大部分之间差1, 待验证
//基本解决, 主要原因是C#的字符串序号从0开始, 而DELPHI的从1开始
end;
----------------------------------------------
-
直接用Delphi开发网络应用程序
http;//www.web0000.com
作者：
(FengLinYuShu) ▲▲▲▲▲ -
盒子活跃会员
2015-8-16 9:57:23
8楼： 不过, 我是想得到具体的步骤,
类似, 第一步: 增加一个字符K, 第二步, 删除一个字符D,...
有什么好办法呢?
----------------------------------------------
-
直接用Delphi开发网络应用程序
http;//www.web0000.com
作者：
(cafetoi) ▲▲▲△△ -
注册会员
2015-8-16 19:05:15
9楼： 這裡還有一個
http://www.codeproject.com/Articles/508682/StringpluscomparisonplusinplusDelphi ;
另外, 在 debug 模式下, 單步執行應該可以看出每一步的執行的結果...
----------------------------------------------
-
作者：
(FengLinYuShu) ▲▲▲▲▲ -
盒子活跃会员
2015-8-16 19:21:22
10楼： TO 楼上:
你的网址打不开. 虽然DEBUG可以看到每步的结果, 但还是看不出来.
这个算法很有技巧, PFPF! 不是我原来想的笨笨的办法
----------------------------------------------
-
直接用Delphi开发网络应用程序
http;//www.web0000.com
作者：
(cafetoi) ▲▲▲△△ -
注册会员
2015-8-16 21:39:35
11楼： 以下是
http://www.codeproject.com/Articles/508682/StringpluscomparisonplusinplusDelphi ;中的原碼 (我不懂 Delphi (Pascal), 我用 C++ Builder 2012) 但工作需要用到 diff 算法, 無意中看到這個)
==========
unit StringComparison;
interface
uses
Math, Generics.Collections;
type
TDiff = record
Character: Char;
CharStatus: Char; //Possible values: [+, -, =]
end;
TStringComparer = class
strict private
type TIntArray = array of array of Integer;
class function LCSMatrix(X, Y: string): TIntArray;
class procedure ComputeDifferences(aLCSMatrix: TIntArray;
X, Y: string;
i, j: Integer;
aDifferences: TList<TDiff>);
public
class function Compare(aString1, aString2: string): TList<TDiff>;
end;
implementation
{ TStringComparer }
class function TStringComparer.LCSMatrix(X, Y: string): TIntArray;
var
m, n,
i, j: Integer;
begin
m:= Length(X);
n:= Length(Y);
//We need one extra column and one extra row to be filled with zeroes
SetLength(Result, m + 1, n + 1);
//First column filled with zeros
for i := 0 to m do
Result[i, 0] := 0;
//First row filled with zeros
for j:= 0 to n do
Result[0, j]:= 0;
//Storing the lengths of the longest common subsequences
//between prefixes of X and Y
for i:= 1 to m do
for j:= 1 to n do
if X[i] = Y[j] then
Result[i, j] := Result[i-1, j-1] + 1
else
Result[i, j]:= Max(Result[i, j-1], Result[i-1, j]);
end;
class procedure TStringComparer.ComputeDifferences(aLCSMatrix: TIntArray;
X, Y: string;
i, j: Integer;
aDifferences: TList<TDiff>);
var
CharDiff: TDiff;
begin
if (i > 0) and (j > 0) and (X[i] = Y[j]) then
begin
ComputeDifferences(aLCSMatrix, X, Y, i-1, j-1, aDifferences);
CharDiff.Character:= X[i];
CharDiff.CharStatus:= '='; //The character did not change
aDifferences.Add(CharDiff);
end
else
if (j > 0) and ((i = 0) or (aLCSMatrix[i,j-1] >= aLCSMatrix[i-1,j])) then
begin
ComputeDifferences(aLCSMatrix, X, Y, i, j-1, aDifferences);
CharDiff.Character:= Y[j];
CharDiff.CharStatus:= '+'; //The character was added
aDifferences.Add(CharDiff);
end
else if (i > 0) and ((j = 0) or (aLCSMatrix[i,j-1] < aLCSMatrix[i-1,j])) then
begin
ComputeDifferences(aLCSMatrix, X, Y, i-1, j, aDifferences);
CharDiff.Character:= X[i];
CharDiff.CharStatus:= '-'; //The character was removed
aDifferences.Add(CharDiff);
end;
end;
//This is a factory method
class function TStringComparer.Compare(aString1, aString2: string): TList<TDiff>;
var
Matrix: TIntArray;
begin
Result:= TList<TDiff>.Create;
Matrix:= LCSMatrix(aString1, aString2);
ComputeDifferences(Matrix,
aString1, aString2,
Length(aString1), Length(aString2),
Result);
end;
end.
----------------------------------------------
-
作者：
(鱼子酱) ▲▲△△△ -
注册会员
2015-8-18 8:32:20
12楼： 就是算最短编辑距离嘛，
那么一共三种编辑
1.插入一个字符
2.修改一个字符
3.删除一个字符
很普通的一个算法问题。
最蠢的就是用递归遍历求最小编辑距离。
正常的解法使用动态规划。
定义s[i,j] 代表前一个字符取到i个后一个字符串取到j个时的最短编辑距离
然后手机打字太累懒得打递推公式了......
----------------------------------------------
-我的网站:
http://www.vlabpro.com/ 几个中学生用Delphi 制作的软件平台
作者：
(FengLinYuShu) ▲▲▲▲▲ -
盒子活跃会员
2015-8-18 8:48:13
13楼： TO 11楼:
这个算法是经典的算法, 我已经实现了,也可以求出具体过程. 但 注意这里:
type TIntArray = array of array of Integer;
如果字符串长度太长, 会占太多内存.
目前已经找到一个小内存版的, 但求不出具体过程了,
TO 12楼;
道理很简单,实现很丰满
----------------------------------------------
-
直接用Delphi开发网络应用程序
http;//www.web0000.com
作者：
(cafetoi) ▲▲▲△△ -
注册会员
2015-8-18 10:03:17
14楼： 是否有可以比較中文夾雜 UnicodeString 的? 例如:
a: 定义s[i,j] 代表前一个字符取到j，个后一个字符串取到j个时的最短编辑距離
^^^ ^^ ^^
b: 定义s[i,j] 代表前一个字符取到i个后一个字符串取到j个时的最長编辑距离
^ ^^ ^^
----------------------------------------------
-
作者：
(cafetoi) ▲▲▲△△ -
注册会员
2015-8-18 10:05:03
15楼： 抱歉, 上一貼本想用 ^^ 標示增刪位置, 但貼出後位置走了....
----------------------------------------------
-
作者：
(FengLinYuShu) ▲▲▲▲▲ -
盒子活跃会员
2015-8-18 16:55:49
16楼： TO cafetoi:
可以
----------------------------------------------
-
直接用Delphi开发网络应用程序
http;//www.web0000.com
作者：
(cafetoi) ▲▲▲△△ -
注册会员
2015-8-19 5:35:30
17楼： 我用這個 (只懂皮毛 C++) https://github.com/cubicdaiya/dtl 費了九牛二虎之力改了一下
----------------------------------------------
-
作者：
(乐天无极) ▲▲△△△ -
注册会员
2016-3-21 17:58:27
18楼： delphi版:
simhash
地址：
http://www.it610.com/article/1862088.htm----------------------------------------------
相信自己，若自己都不相信，那还有谁可信。
