英文分割，求最快速度算法 ( 积分: 300 )

好好，大家多多提建议，可以另外开贴加分

to errorcode

用hash如何做呢？给点例子

不是极度追求速度，没必要使用哈希表，哈希是用空间（内存）换时间。
如果一定要用，delphi提供了Thashedstringlist类可以使用
在IniFiles单元内，注意uses IniFiles单元。

这么小的数据量，hash表的作用不明显，因为hash的构造需要时间，而且使用hash还要考虑到你的数据类型，是否冲突多，如果冲突多，那么需要调整散列算法，否则效率也很低的。

{
测试结果：1.5M的文档，分出17475个单词，10352(ms)
因为中途处理了两次，一次只5000(ms)左右，目前是最快的了,但是这样的处理
结果还是不够理想。


procedure TForm1.Button3Click(Sender: TObject);
var
EnDiv: TPartList;
begin

EnDiv := TPartList.Create(self.Memo1.Text);
try
if EnDiv.DivList <> nil then
begin
self.Memo2.Text := EnDiv.DivList.Text;
self.Caption := Format('UseTime: %s, 总单词数: %d, 总长度：%d',
[FormatDateTime('hh:nn:ss.zzz', EnDiv.UseTime), EnDiv.DivList.Count, EnDiv.DocSize]);
end;
finally
FreeAndNil(EnDiv);
end;
end;

}
unit EN_Part;

interface

uses
Windows, SysUtils, Classes;


type
TPartList = class
private
FUseTick: Cardinal
//处理时间（毫秒)
FUseTime: TDateTime
//处理时间
FDocument: string
//文档内容
FDocSize: Integer
//大小
FDivList: TStringList
//结果

procedure LoadFile(const FileName: string);//加载文件
procedure ParseDiv
//处理分词
public
constructor Create(const sDoc: string
const FileName: string = '');
destructor Destroy
override;
//文档内容
property Document: string read FDocument;
//结果词
property DivList: TStringList read FDivList;
//文档大小
property DocSize: Integer read FDocSize;
//处理时间
property UseTick: Cardinal read FUseTick;

property UseTime: TDateTime read FUseTime;
end;



implementation

{ TPartList }

constructor TPartList.Create(const sDoc, FileName: string);
begin
inherited Create;
FDivList := nil;
FDocSize := 0;
FUseTime := 0;

FUseTime := Now;
FUseTick := Windows.GetTickCount;
if FileExists(FileName) then
LoadFile(FileName)
else if Trim(sDoc) <> '' then
begin
FDocSize := Length(sDoc);
SetLength(FDocument, FDocSize);
System.Move(sDoc[1], FDocument[1], FDocSize);
end
else raise Exception.Create('没有发现可用文档内容或文件名。');

self.FDivList := TStringList.Create;
self.ParseDiv;
FUseTick := Windows.GetTickCount - FUseTick;
FUseTime := Now - FUseTime;
end;

destructor TPartList.Destroy;
begin
SetLength(FDocument, 0)
//释放内存string
if FDivList <> nil then begin
FDivList.Clear;
FreeAndNil(FDivList)
//释放列表
end;
inherited Destroy;
end;

{$DEFINE NEW_PARSEDIV}

{$IFDEF NEW_PARSEDIV}
procedure TPartList.ParseDiv;
var
I: Integer;
s1: string;
begin
s1 := '';
try
for I := 1 to FDocSize do
if FDocument in ['a'..'z', 'A'..'Z', '0'..'9', '-', '_'] then
System.Continue
else FDocument := #13;

s1 := FDocument;
for I := 1 to Length(s1) do
if s1 in ['a'..'z', 'A'..'Z'] then
System.Continue
else s1 := #13;

FDivList.Sorted := True;
FDivList.Duplicates := dupIgnore;
FDivList.Text := s1 + FDocument;
finally
s1 := '';
end;
end;

{$ELSE}
procedure TPartList.ParseDiv;
function SubParse(const S: string): string;
var
I: Integer;
begin
Result := '';
for I := 1 to Length(S) do
if S in ['a'..'z'] then //到这儿只有小写了
Result := Result + S
else
Result := Result + #13;

//如果只是一个单词
if Result = S then Result := '';
if (Result <> '') and (Result[Length(Result)] <> #13)then
Result := Result + #13;
end;

var
I: Integer;
s1, s2: string;
begin
s1 := '';
s2 := '';
try

for I := 1 to FDocSize do
if FDocument in ['a'..'z', 'A'..'Z', '0'..'9', '-', '_'] then
s1 := s1 + lowercase(FDocument)
else if s1 <> '' then begin
s2 := s2 + s1 + #13;
//s2 := s2 + SubParse(s1);
s1 := '';
end;

FDivList.Sorted := True;
FDivList.Duplicates := dupIgnore;
FDivList.Text := s2;
finally
s1 := '';
s2 := '';
end;

end;
{$ENDIF}

procedure TPartList.LoadFile(const FileName: string);
var
hFile: THandle;
len: Integer;
begin
hFile := FileOpen(FileName, SysUtils.fmOpenRead);

if hFile = INVALID_HANDLE_VALUE then
//打开文件句柄失败，抛出错误
raise Exception.Create(SysUtils.SysErrorMessage(Windows.GetLastError));

try
FDocSize := FileSeek(hFile, 0, FILE_END);
FileSeek(hFile, 0 ,FILE_BEGIN);

SetLength(self.FDocument, FDocSize);
len := FileRead(hFile, Pointer(FDocument)^, FDocSize);
if len <> FDocSize then
begin
//读取文件数据失败，抛出错误
raise Exception.Create(SysUtils.SysErrorMessage(Windows.GetLastError));
end;
finally
FileClose(hFile);
end;
end;

end.

因我的文件暂时可能会不大，以后积累多可能会很大，几十MB都有的，所以求最快速度。

for I := 1 to FDocSize do
if FDocument in ['a'..'z', 'A'..'Z', '0'..'9', '-', '_'] then
System.Continue
else FDocument := #13;

s1 := FDocument;
for I := 1 to Length(s1) do
if s1 in ['a'..'z', 'A'..'Z'] then
System.Continue
else s1 := #13;
处理两次干吗？
下面这次只是把 '0'..'9', '-', '_' 也改为 #13而已，把上面那个循环去掉，结果是完全一样的。

另外，尽量避免在循环内使用 s1 := s1 + lowercase(FDocument)
之类的字符串重组语句。
因为就这么一个简单的语句，会导致内存的重新分配，
分配和释放内存是耗时的操作。

用二分法，处理数度不会按文件增长的整数倍增加的，他们的关系是Log(N ),n=单词数量。
用哈希表，则要考虑一个内存大小（不是说10M的文件就占用10M内存，不够的，要远大于这个数量），如果哈希表过大，那么超出物理空余内存时，系统会使用磁盘缓冲，这时性能会急剧下降。而如果哈希表过小，那么冲突会大量增加，同样导致性能下降。因此，打算使用哈希表，那么需要考虑合适的散列函数来构造。

tstringlist的Sorted:=true以后，会自动使用二分法查找
且tstringlist默认是不区分大小写的。
如需区分大小写，设置 CaseSensitive为true。
设置大小写区分，应该会有少许性能提升，因为省去了大小写转换过程

谢谢ufo!您 的热心回复， 重复一次的原因是这样
如果这样的词我要分两次，
hs-kill可以分成
1.hs-kill
2.hs
3.kill
连在一起我要，分开还要一次

这样啊，那也不用处理两次啊，基于统计得知，含有-的单词毕竟是少数，可以这样做：
if ss in['a'..'z'] then
Continue
else if ss in ['A'..'Z'] then
Continue
else if ss in ['0'..'9'] then
Continue
else if ss in ['-'] then
begin
把当前的i值保存到一个数组
Continue
end else ss:= #13;
这样可以大幅减少判断的数量，因为小写字母多，可以很快跳过

多人接受答案了。

晕，看来偶昨天光顾打CH是错误，白忙呼ing

hash很难吗？好像我只加了20行不到的代码。。。。
反正俺在30M的文本下是1s下的处理速度，嘎嘎

errorcode
你发上来，我另外开贴给分

to:errorcode，如果确实有如此效果，我也给你300分。

本着技术交流的精神，我先作如下猜测：
添加不到20行代码来建立哈希表的应用，应该是使用了delphi的现成类。
delphi6下的哈希string类我前几天试了，处理了一个1.77M的文本。速度和tstringlist差不多。
如果不做重复单词检查（直接把st1.Sorted:= true;
st1.Duplicates := dupIgnore;这两行注释掉即可）

那么我分割55万个单词，用tstringlist也是在一秒以下完成。

不过，技术无止境，还是非常期待errorcode的大作。

看上面的代码，已修改。

看AddHash函数，Hash函数我只是用了个简单的函数，只实现了一个简单处理冗佘的法子。

好像加加减减不止20行。。。不过应该是很简单的，昨天是乱数行数。。。。

to:errorcode,
我试了你的代码，速度确实比我的代码快，但数据不对，原先2500多个的，在你的代码处理后只剩1600余个，估计是哈希函数有问题，一些不重复的单词被误认为重复了。

我修改了一下你的GetHashValue函数
现在能返回结果 2521个，与原先的2564个相差不多了。
速度确实比我的方法快，1.77M 的文件处理时间在1秒以内。
现等待楼主用他自己的数据再测试一下看看单词纰漏情况如何，
修改后的函数如下：
function GetHashValue(const Buf
Len: Integer
HashSeed: Cardinal
IgnoreCase: Boolean = False): Cardinal;
var
P: PChar;
I: Integer;
CharByteArray: ^TCharToByteValue;
begin
Result := HashSeed;
P := @Buf;
CharByteArray := @CHAR_2_BYTEs[IgnoreCase];
for I := 1 to Len do
begin
result:=((Result shl 2) or (Result shr (SizeOf(Result) * 8 - 2))) xor
Ord(CharByteArray[P^]);
inc(p);
end;
end;

我也测出相同的问题，原来的16000多单词变4000多，他的检查重复我不敢用了

再次对errorcode的代码进行了画蛇添足，修改了AddHash函数内的语句，
errorcode应该是用了链地址抗冲突法，对冲突的判断只是简单的比较一下字符串长度和hash值，准确性有纰漏，我改为直接比对内存，代码如下：
//......................AddHash函数内
IsFind := False;
while Hash <> nil do
begin
IsFind := CompareMem(Hash.Str.buf, AStr.buf,AStr.len) and (Hash.HashData = HashData)
//修改了这句
if IsFind then break;
Hash := Hash.Next;
end;
//......................

这样改动后，处理时间稍有延长，且数据变为2730余个，多起来了。
具体多在哪里，还请楼主自行修正。
因为我这里的测试数据是中英文混合的，可能结果不准确。