大きい辞書の単語セットの大文字と小文字の変換

Question

大文字と小文字を区別しないで、辞書の単語を一致させようとしています。私の初期のアプローチ は次のようになります：

1. read dict;すべての単語を小文字に変換し、セットに格納します。
2. セット

のメンバーシップのチェック新しい単語はこれを達成するためのより良い（より効率的な）方法はありますか？私はハスケルにとって初めてです。

Answer 1

私はちょうどTextと一緒に、Stringsに変換するのではなく、代わりに使用します。

Data.Text.IOは、ファイルからテキストを読み取るためhGetContents、readFileなどのバージョンが含まれており、Data.Textは、テキストのためのlinesを持っています。 T.tolowerとT.linesを使用することにより

{-# LANGUAGE OverloadedStrings #-} 
import System.IO 
import qualified Data.Text as T 
import qualified Data.Text.IO as T 
import qualified Data.Set as S 

main = do 
    let path = "/usr/share/dict/american-english" 
    h <- openFile path ReadMode 
    hSetEncoding h utf8 
    contents <- T.hGetContents h 
    let mySet = (S.fromList . map T.toLower . T.lines) contents 
    putStrLn $ show $ S.member "acadia" mySet 

我々は、明示的なパック/アンパック呼び出しを避けます。

mySetは、StringsではなくText値のセットになりました。 を使用すると、OverloadedStringsプラグマのリテラル"acadia"は、テキスト値として と解釈されます。

Answer 2

はい、あなたが提案するものは妥当です。メインの質問にほとんど関係のないいくつかのいくつかの発言は、：

1. それだけでTextなくString使用してあなたの自己を制限する方が効率的でしょう。
2. toCaseFoldの機能をtoLowerに設定することをお勧めします。この場合は、より適切です。

Answer 3

あなたは私の最初の答えが役に立ったと評価していますが、

は

私は単に単一延ByteStringとして全体の辞書を読み込み、単語を調べるために書いて尻込みソルバが実行...私は別のアプローチを提案してみましょうByteStringのバイナリ検索。

辞書は既にソートされていて、小文字に正規化されていなければなりませんが、辞書は静的であり、事前にわかっているので問題ありません。

もちろん、バイナリ検索を実行するときに(lo+hi)/2を計算すると、単語の真ん中に位置する可能性があるので、現在の単語の先頭にバックアップするだけです。

この主な利点は、辞書の読み込みが非常に高速でメモリ効率が良いことです。さらに、検索アルゴリズムは良好なメモリ局所性を有する。私はそれを測定していませんが、Data.Setを作成すると生データのサイズを2倍以上にすると驚くことはありません。

コードはここにあります：https://github.com/erantapaa/hoggle