Suffix ArrayをRustで実装した

suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog; を読んで、ちょうど自分も何らかの形で全文検索を一部実装してみようと思っていたのでRustで真似してみました。

Rustを選んだ理由は、以下の理由からです。

• 実際に全文検索を実装するのに耐えうるパフォーマンスであること
• パッケージマネージャなどのエコシステムが完備されていること

Rustについてはそれほど詳しくはないのですが、GCや例外がないとのこと。であればパフォーマンスチューニングがC言語並にやりやすい可能性がありますし、一度真面目に勉強してみたいと思っていました。Goと異なり、ジェネリクスがあるのも魅力的です。

というわけでコードこんな感じになりました:

pub fn make_suffix_array(s: &str) -> Vec<i64> {
  use std::collections::HashMap;

  let mut map = HashMap::new();

  for i in 0..s.len() {
    map.insert(&s[i..s.len()], i as i64);
  }

  use std::iter::FromIterator;

  let mut suffixes = Vec::from_iter(map.keys());
  suffixes.sort();

  return suffixes.iter().map(|suffix| *map.get(*suffix).unwrap()).collect();
}

#[test]
fn test_make_suffix_array() {
  let a = make_suffix_array("banana");
  assert_eq!(a, vec![5, 3, 1, 0, 4, 2]);
}

Rustに慣れていないので、この数十行を書くのも大変でしたがとりあえず動きます。エディタはIntelliJ Rustを使いました。あまり賢くはないもののコード補完があり、普段使っているRubyMineやAndroid Studioに近い感覚でコードを書けるのでわりと好印象です。