3

私は最近、文字列を処理し、そのすべての部分文字列を見つけて、辞書にあるもののリストを保持する Scala コードを書きました。全体的な文字列内の部分文字列の開始と終了も、後で使用するために保持する必要があるため、これを行う最も簡単な方法は、次のようなネストされた for ループを使用することです。

for (i <- 0 until word.length)
  for (j <- i until word.length) {
    val sub = word.substring(i, j + 1)
    // lookup sub in dictionary here and add new match if found
  }

演習として、Haskell で同じことをやってみることにしました。部分文字列のインデックスがなくても十分簡単に​​思えます。このアプローチのようなものを使用して部分文字列を取得し、再帰関数を呼び出して一致を蓄積することができます。しかし、インデックスも必要な場合は、よりトリッキーに思えます。

「親」文字列内の開始インデックスと終了インデックスとともに、連続する各サブ文字列を含むリストを返す関数をどのように作成しますか?

たとえばtokens "blah"、[("b",0,0), ("bl",0,1), ("bla",0,2), ...]

アップデート

答えの素晴らしい選択と探索する新しいものがたくさんあります。少しいじった後、私は最初の答えに行きました.Danielの使用を許可するという提案で[0..].

data Token = Token String Int Int 

continuousSubSeqs = filter (not . null) . concatMap tails . inits

tokenize xs = map (\(s, l) -> Token s (head l) (last l)) $ zip s ind
    where s = continuousSubSeqs xs
          ind = continuousSubSeqs [0..]

私の限られた Haskell の知識を考えると、これは比較的理解しやすいように思えました。

4

4 に答える 4

2 
import Data.List

continuousSubSeqs = filter (not . null) . concatMap inits . tails

tokens xs = map (\(s, l) -> (s, head l, last l)) $ zip s ind
    where s   = continuousSubSeqs xs
          ind = continuousSubSeqs [0..length(xs)-1]

このように動作します：

tokens "blah"
[("b",0,0),("bl",0,1),("bla",0,2),("blah",0,3),("l",1,1),("la",1,2),("lah",1,3),("a",2,2),("ah",2,3),("h",3,3)]
于 2012-07-15T22:05:06.773 に答える
1

あなたが書いた 2 つのネストされたループは、優れた出発点です。つまり、その作業を 2 つの再帰関数に委譲し、ループに対応する関数を作成できtokensます。outerinner

type Token a = ([a], Int, Int)

tokens :: [a] -> [Token a]
tokens = outer 0
  where
    outer _ []         = []
    outer i l@(_ : xs) = inner i [] l ++ outer (i + 1) xs
      where
        inner _ _ []         = []
        inner j acc (x : xs) =
          (acc ++ [x], i, j) : inner (j + 1) (acc ++ [x]) xs

ここではouter、文字列を繰り返し処理し、その文字列内の開始位置ごとに、innerその位置で開始するすべてのセグメントとその終了位置を収集する呼び出しを行います。

この機能は要件を満たしていますが、

> tokens "blah"
[("b",0,0),("bl",0,1),("bla",0,2),("blah",0,3),("l",1,1),("la",1,2),("lah",1,3),("a",2,2),("ah",2,3),("h",3,3)]

リストの連結が繰り返されるため、非常に非効率的です。より効率的なバージョンでは、結果がいわゆる差分リストに蓄積されます。

type Token a = ([a], Int, Int)

tokens :: [a] -> [Token a]
tokens l = outer 0 l []
  where
    outer _ []         = id
    outer i l@(_ : xs) = inner i id l . outer (i + 1) xs
      where
        inner _ _ []         = id
        inner j acc (x : xs) =
          ((acc [x], i, j) :) . inner (j + 1) (acc . (x :)) xs

もちろん、辞書の作成方法は、それをどのように表現するかによって異なります。これは、単純な順序付き連想リストを使用するアプローチです。

type Dict a = [([a], [(Int, Int)])]

empty :: Dict a
empty = []

update :: Ord a => Token a -> Dict a -> Dict a
update (xs, i, j) []                = [(xs, [(i, j)])]
update (xs, i, j) ((ys, ns) : dict) = case compare xs ys of
  LT -> (xs, [(i, j)]) : (ys, ns) : dict
  EQ -> (ys, (i, j) : ns) : dict
  GT -> (ys, ns) : update (xs, i, j) dict

toDict :: Ord a => [a] -> Dict a
toDict = foldr update empty . tokens

ただし、キーは文字列であるため、試行(別名プレフィックス ツリー) を使用することをお勧めします。

あなたが求めているのが効率的な部分文字列クエリである場合は、サフィックスツリーを調べることをお勧めしますが、それらの実装は多少複雑です。あなたはチェックアウトしたいかもしれません

  • ロバート・ギーゲリッチとステファン・クルツ。命令型と純粋に関数型のサフィックス ツリー構造の比較。コンピューター プログラミングの科学25(2–3):187–218、1995

Hackageの Bryan O'Sullivan のsuffixtreeパッケージ。

于 2012-07-16T07:00:15.700 に答える
1

UNIX パイプに似た、左から右に読みやすい別のバージョン

import Data.List
import Control.Category 

tokens = 
     tailsWithIndex
     >>> concatMap (\(i,str) -> zip (repeat i) (initsWithIndex str))
     >>> map adjust
     where
       tailsWithIndex = tails >>> init >>> zip [0..]
       initsWithIndex = inits >>> tail >>> zip [0..]
       adjust (i, (j, str)) = (str, i, i+j)

サンプルラン

>tokens "blah" 
[("b",0,0),("bl",0,1),("bla",0,2),("blah",0,3),("l",1,1),("la",1,2),("lah",1,3),("a",2,2),("ah",2,3),("h",3,3)]

が遅延している場合concatMap、生のリスト アクセスの代わりに Data.List 関数を使用することを除いて、計算全体が遅延し、効率的になります。

于 2012-07-16T09:22:22.260 に答える
1

私のバージョン:

import Data.List

tokens = 
  map join . filter (not . null) . concatMap inits . tails . zip [0..]
  where 
    join s@((i, _):t) = 
      (map snd s, i, foldl' (\_ i -> i) i (map fst t))

main =
  putStrLn $ show $ tokens "blah"

-- [("b",0,0),("bl",0,1),("bla",0,2),("blah",0,3),("l",1,1),("la",1,2),("lah",1,3),("a",2,2),("ah",2,3),("h",3,3)]

更新：

import Control.Arrow

...

tokens = 
  map join . filter (not . null) . concatMap inits . tails . zip [0..] where 
    join s = (s', i, j) where 
      ((i, j), s') = (first (head &&& last)) $ unzip s

...
于 2012-07-16T00:14:32.963 に答える