C#で文字列検索には、string.Containsメソッドやstring.IndexOfメソッドを使用してきました。しかし、これらの方法より速く検索できる方法があるのでないのかと思い、調べたところ、接尾辞配列(suffix array)というものが文字列検索で利用されている記事が多くあったことから、実装してみました。
接尾辞配列(suffix array)
接尾辞配列（せつびじはいれつ）やサフィックス・アレイ（英: suffix array）とは、文字列の接尾辞（開始位置を異にし終端位置を元の文字列と同じくする部分文字列）の文字列中の開始位置を要素とする配列を、接尾辞に関して辞書順に並べ替えて得られる配列である。
(引用先)：Wikipedia 接尾辞配列
使用環境
- Visual Studio Community 2017
- .NET Framework 4.6.1
- C# 7.1
実装コード
まず、接尾辞配列を作成するメソッドを作成しました。
//文字列探索クラス
public class SearchEx
{
private string _text = string.Empty;
private int[] _suffixArray;
//コンストラクタ
public SearchEx(string text)
{
if (string.IsNullOrEmpty(text)) throw new ArgumentNullException(nameof(text));
this._text = text;
this.CreateSuffixArray();
}
//(中略)
//接尾辞配列作成メソッド
private void CreateSuffixArray()
{
//連番配列を作成
var suffixArray = Enumerable.Range(0, this._text.Length).ToList();
//ソート部分
suffixArray.Sort(
(x, y) =>
{
return string.Compare(this._text, x, this._text y, this._text.Length);
});
this._suffixArray = suffixArray.ToArray();
}
}
改善点その1 連番配列作成
動作には問題なかったのですが、接尾辞配列を作成しているCreateSuffixArrayメソッドがかなり時間を使っていました。確認したところ、連番の配列を作成する際、Enumerable.Rangeで列挙したオブジェクトをToListメソッドで実体化させて作成していましたが、要素数が多くなるとかなり時間がかかっていました。ToArrayメソッドでも試してみましたが、少しだけ速くなった程度でした。
そのため、Enumrable.Rangeではなく、普通に配列を作成してforループで値を代入したところ、速度は改善しました。
//接尾語配列生成メソッド
private void CreateSuffixArray()
{
//実体化にかなり時間がかかる
//var suffixArray = Enumerable.Range(0, this._text.Length.ToList();
//配列を作成後、数値を代入する
var suffixArray = new int[text.Length];
for (var index = 0; index < text.Length; index++)
{
suffixArray[index] = index;
}
(中略)
}
※Enumrable.Range.ToListとEnumrable.Range.ToArrayと配列生成+forループの3種類で、0～10000の連番配列を1000回作成した時間を測定しました。測定にはStopWatchクラスを使用しました。
| 種類 | 実行時間 |
|---|---|
| Enumrable.Range.ToList | 345ms |
| Enumrable.Range.ToArray | 302ms |
| 配列生成+forループ | 94ms |
var watch = Stopwatch.StartNew();
//Enumrable.Range.ToList
for (var i= 0;i<1000;i++)
{
var list = Enumerable.Range(0, 10000).ToList();
}
watch.Stop();
Console.WriteLine($@"Enumerable.Range.ToLis{watch.ElapsedMilliseconds}");
watch.Restart();
//Enumrable.Range.ToArray
for (var i = 0; i < 1000; i++)
{
var list = Enumerable.Range(0, 10000).ToArray();
}
watch.Stop();
Console.WriteLine($@"Enumerable.Range.ToArra{watch.ElapsedMilliseconds}");
watch.Restart();
//配列生成+forループ
for (var i = 0; i < 1000; i++)
{
var list = new int[10000];
for (var index = 0; index < list.Length; index++)
{
list[index] = index;
}
}
Console.WriteLine($@"new Int{watch.ElapsedMilliseconds}");
改善点その2 ソート
次に、Sort部分がかなり時間がかかっていました。そのため、List.Sortの内部動作をReference Sourceで確認したところ、ソートに関してはArray.Sortが行っていることがわかったので、ソート部分をArray.Sortに変更し、文字列比較にもstring.Compareからif文やnull判定など無くしたCultureInfo.CurrentCulture.CompareInfo.Compareにしましたが、そこまで大きく速度は変化しませんでした。
private void CreateSuffixArray()
{
var textSize = this._text.Length;
if (textSize >= int.MaxValue) throw new OverflowException(nameof(textSize));
this._suffixArray = new int[textSize];
for (var index = 0; index < textSize; index++)
{
this._suffixArray[index] = index;
}
//Array.Sortに変更。
Array.Sort(
this._suffixArray,
(x, y) => InternalCompare(x, y, textSize));
}
//文字列比較用メソッド
private int InternalCompare(int indexA, int indexB, int maxLength)
{
return CultureInfo.CurrentCulture.CompareInfo.Compare(
this._text,
indexA,
(maxLength - indexA),
this._text,
indexB,
(maxLength - indexB),
CompareOptions.None);
}
結果
やはり、接尾辞配列作成の際に使用するソート部分にかかる時間を何とかしないと、実用的には使えなさそうです。接尾辞配列の構築の高速化には、SA-IS法というものがあるらしいので、次回に実装して速度を確認してみます。今日のところはこのくらいで...。
何か間違い、良い方法などあればコメントで情報提供よろしくお願いします。