テキストに現れる単語の頻度を高速でカウントするには？

解決

deldel 2004-07-14 07:02:15 No: 9900

数百キロバイトのテキストから、出現する英単語の頻度をカウントしたいと思い次のようなコードを書きました。
これでは、処理に非常に時間がかかってしまい、実用的ではありません。もっと早くカウントする方法を教えていただけないでしょうか。

var
sr, word, hash:TStringList;
i, hindo:integer;
reg:TRegExpr;

begin
reg:=TRegExpr.Create;
sr:=TStringList.Create;
hash:=TStringList.Create;
word:=TStringList.Create;

sr.LoadFromFile(filename);
reg.Expression:='[\s\b]+';
reg.Split(sr.Text, word);
for i := 0 to word.Count-1 do
begin
  if  hash.IndexOfName(word.Strings[i]) = -1 then
  begin
   hash.Add(word.Strings[i]+'=1');
   end
  else
  begin
   hindo:=StrToInt(hash.Values[word.Strings[i]])+1;
   hash.Values[word.Strings[i]]:=IntToStr(hindo);
   end;
end;

RichEdit1.Text:=hash.Text;

jok 2004-07-14 07:54:34 No: 9901

速度については自信がないのですが、いちいちハッシュ値を検索するのはいかにも
無駄なような気がします。簡単に思いつくのは、すべての単語を TStringList に
Add してから、Sort し、並んだ順で、重複している数を数えると速いと思います。

にしの 2004-07-14 08:55:15 No: 9902

空白で区切られた文字列を単語とするんですよね？
正規表現は遅いです。単純な字句解析なら、普通にコーディングした方が早いですよ。
また、hashとしていますが実体はTStringListですよね。
検索は単純検索ですので、これもまた自前で作成した方がよいです。
二分探索木あたりが適切かと思います。

にしの 2004-07-14 20:07:12 No: 9903

正規表現を使わなくするだけでもかなり違いますね。

こんな感じでどうでしょう。

procedure TForm1.Button2Click(Sender: TObject);
var
  sr, hash:TStringList;
  i, hindo:integer;
  S, w: String;
  c: integer;
  p, np: PCHAR;
begin
  sr:=TStringList.Create;
  hash:=TStringList.Create;
  hash.CaseSensitive := True;
  sr.LoadFromFile('C:\Program Files\Borland\Delphi7\Source\Rtl\Win\UxTheme.pas');//Windows.pas'); // Windows.pasだと時間がかかりすぎました^^;
  S := sr.Text;
  p := PCHAR(S);
  while p^ <> #0 do
  begin
    //空白をスキップ
    while p^ in [#9, #10, #13, ' '] do
    begin
      Inc(p);
    end;
    np := p;
    c := 0;
    //単語を取得
    while not (np^ in [#0, #9, #10, #13, ' ']) do
    begin
      Inc(np);
      Inc(c);
    end;
    SetLength(w, c);
    CopyMemory(PCHAR(w), p, c);
    SetLength(w, c);
    p := np;
    //単語をカウント
    i := hash.IndexOf(w);
    if i >= 0 then
    begin
      hash.Objects[i] := TObject(integer(hash.Objects[i]) + 1);
    end
    else
    begin
      hash.AddObject(w, TObject(1));
    end;
  end;
  EditorEx1.Lines.Clear;
  for i := 0 to hash.Count - 1 do
  begin
    EditorEx1.Lines.Add(hash[i] + '=' + IntToStr(Integer(hash.Objects[i])));
  end;
  hash.Free;
  sr.Free;
end;

気になったのですが、TStringListのCaseSensitiveを設定してやらないと、大文字小文字の区別をしないと思うのですが、それでよいのでしょうか。

二分探索木は前に作ったのですがファイル管理用でして、ハッシュとして使うには変更点が多いので^^;
もしやられるのであれば、自力でがんばってください。

deldel 2004-07-14 22:01:17 No: 9904

deldelです。
jokさま、にしのさま、
ご回答いただき、ありがとうございました。

とりあえず、正規表現を使わず単語を取り出すためにコードを書いていましたが、半角空白が２つ続くと動作しないという情けないもので、困りきっておりました。

こうしてコードまで書いていただいて、本当にありがとうございます。「なるほど」と思う部分ばかりです。

大文字小文字は区別してはいけないので、CaseSensitiveを設定する必要がありますね。

二分探索木を完成させるまでの道のりは長そうですが、なんとかがんばってみたいと思います。

それでは、失礼いたします。