---
title: Go言語に接尾辞配列(Suffix Array)が組み込まれていた
tags: []
categories: ["Programming", "Golang", "index", "suffixarray"]
date: 2013-08-06T15:50:31Z
updated: 2013-08-06T15:50:31Z
---

Go言語の標準ライブラリをぱらぱらっとみていたら気になる物が

`index/suffixarray`

その名の通り接尾辞配列(Suffix Array)実装ですね。
こんなものが標準で組み込まれているなんてさすがGoogle製。

(ちなみに[以前Javaで実装してました][1])

`suffixarray.New([]byte)`でインデックスをビルドして、
`Lookup([]byte, int)`で検索。第2引数は最大取得件数で-1にすれば全件取得。
返り値は第1引数の文字列から始まる部分文字列の位置の配列。

試してみた。

    package main
    
    import (
            "fmt"
            "index/suffixarray"
    )
    
    func main() {
            input := "abracadabra"
            index := suffixarray.New([]byte(input))
    
            // "abracadabra"のうちraから始まる文字列を表示
            fmt.Println("begin from 'ra'")
            fmt.Print("\t")
            for _, value := range index.Lookup([]byte("ra"), -1) {
                    fmt.Print(input[value:], " ")
            }
            fmt.Println()

             // "abracadabra"のうちabから始まる文字列を表示   
            fmt.Println("begin from 'ab'")
            fmt.Print("\t")
            for _, value := range index.Lookup([]byte("ab"), -1) {
                    fmt.Print(input[value:], " ")
            }
            fmt.Println()
    
            // "abracadabra"のうちbrから始まる文字列を表示
            fmt.Println("begin from 'br'")
            fmt.Print("\t")
            for _, value := range index.Lookup([]byte("br"), -1) {
                    fmt.Print(input[value:], " ")
            }
            fmt.Println()
    }

実行結果

    $ go run suffixarray.go
    begin from 'ra'
    	ra racadabra
    begin from 'ab'
    	abra abracadabra
    begin from 'br'
    	bra bracadabra

Javaのときと同じですね。

Suffix Arrayの初歩について学ぶには↓がおすすめです。

<a href="http://www.amazon.co.jp/%E7%8F%A0%E7%8E%89%E3%81%AE%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E2%80%95%E6%9C%AC%E8%B3%AA%E3%82%92%E8%A6%8B%E6%8A%9C%E3%81%84%E3%81%9F%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E3%82%B8%E3%83%A7%E3%83%B3-%E3%83%99%E3%83%B3%E3%83%88%E3%83%AA%E3%83%BC/dp/4894712369%3FSubscriptionId%3DAKIAJGZ7MSORH7HQ4FJA%26tag%3Dikam-22%26linkCode%3Dsp1%26camp%3D2025%26creative%3D165953%26creativeASIN%3D4894712369 "><img src="http://ecx.images-amazon.com/images/I/51KJSQYQEEL._SL160_.jpg" title="珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造" alt="珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造"></a>


「続・アルゴリズムを学ぼう」にも解説されているらしい。

<a href="http://www.amazon.co.jp/%E7%B6%9A%E3%83%BB%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%82%92%E5%AD%A6%E3%81%BC%E3%81%86-%E5%B7%9D%E4%B8%AD%E7%9C%9F%E8%80%B6/dp/4048913948%3FSubscriptionId%3DAKIAJGZ7MSORH7HQ4FJA%26tag%3Dikam-22%26linkCode%3Dsp1%26camp%3D2025%26creative%3D165953%26creativeASIN%3D4048913948 "><img src="http://ecx.images-amazon.com/images/I/51h0xd2PaHL._SL160_.jpg" title="続・アルゴリズムを学ぼう" alt="続・アルゴリズムを学ぼう"></a>

  [1]: http://blog.ik.am/entry/view/id/78/title/%E6%8E%A5%E5%B0%BE%E8%BE%9E%E9%85%8D%E5%88%97%28Suffix%20Array%29/