homeSoftwaredesign Softwaredesign: Datenmodell Prof. Dr. Uwe Schmidt FH Wedel

Datenmodell


weiter

Das Datenmodell für einen einfachen Wort-Index als Abstrakte Syntax in Haskell Notation

   1module Index
   2where
   3
   4import Data.Char
   5import Data.List(isPrefixOf)
   6
   7import           Data.Map(Map)
   8import qualified Data.Map as M
   9import           Data.Set(Set)
  10import qualified Data.Set as S
  11
  12-- ------------------------------------------------------------
  13--
  14-- data types
  15
  16type Index              = Map Word Occurences
  17
  18type Occurences         = Set Occurence
  19
  20type Occurence          = (DocumentName, Position)
  21
  22type Document           = (DocumentName, WordList)
  23
  24type WordList           = [Word]
  25
  26type DocumentNames      = Set DocumentName
  27
  28-- alias names
  29
  30type Word               = String
  31type DocumentName       = String
  32type Position           = Int
  33
  34-- ------------------------------------------------------------
  35--
  36-- new index
  37
  38emptyIndex      :: Index
  39emptyIndex      = M.empty
  40
  41-- ------------------------------------------------------------
  42--
  43-- basic functions
  44
  45indexDocument   ::                   Document -> Index -> Index
  46indexDocument'  :: (Word -> Bool) -> Document -> Index -> Index
  47
  48deleteDocument  ::               DocumentName -> Index -> Index
  49
  50-- don't filter any words, all are of interest
  51
  52indexDocument   = indexDocument' (const True)
  53
  54-- index a document, but filter uninteresting words
  55
  56indexDocument' isOfInterest (n, wl) ix
  57    = foldr (\ (w', p') ix' -> indexWord w' n p' ix') ix wl2
  58    where
  59    wl1 = map normalize wl
  60    wl2 = filter (isOfInterest . fst) . zip wl1 $ [0..]
  61
  62indexWord       :: Word -> DocumentName -> Position -> Index -> Index
  63indexWord w n p
  64    = M.insertWith S.union w (S.singleton (n,p))
  65
  66deleteDocument n ix
  67    = M.filter (not . S.null)
  68      .
  69      M.map delDoc $ ix
  70    where
  71    delDoc = S.filter ((/= n) . fst)
  72
  73searchIndex     :: Word -> Index -> Occurences
  74searchIndex w
  75    = M.findWithDefault S.empty (normalize w)
  76
  77prefixSearchIndex       :: Word -> Index -> Occurences
  78prefixSearchIndex w
  79    = M.fold S.union S.empty
  80      .
  81      M.filterWithKey (\ k a -> isPrefixOf (normalize w) k)
  82
  83-- projection: forget the positions within a document
  84
  85documentNames   :: Occurences -> DocumentNames
  86documentNames
  87    = S.fold (\ (n, p) ds -> S.insert n ds) S.empty
  88
  89-- ------------------------------------------------------------
  90--
  91-- word processing
  92
  93normalize       :: Word -> Word
  94
  95normalize
  96    = map toLower
  97      .
  98      concatMap remUmlaut
  99    where 
 100    remUmlaut '\196'    = "Ae"
 101    remUmlaut '\214'    = "Oe"
 102    remUmlaut '\220'    = "Ue"
 103    remUmlaut '\228'    = "ae"
 104    remUmlaut '\246'    = "oe"
 105    remUmlaut '\252'    = "ue"
 106    remUmlaut '\223'    = "ss"
 107    remUmlaut c         = [c]
 108
 109scanText        :: String -> WordList
 110scanText        = words . map ( \ c -> if isAlphaNum c then c else ' ')
 111
 112-- ------------------------------------------------------------
 113
 114showIx  :: Index -> IO ()
 115showIx ix
 116    = putStrLn $ concatMap (\ (k,a) -> show k ++ "\t" ++ showPos a ++ "\n") . M.toAscList $ ix
 117    where
 118    showPos
 119        = show . S.toAscList
weiter

weiter

Ein einfaches Testprogramm

   1module IndexTest
   2where
   3
   4import Index
   5
   6-- ------------------------------------------------------------
   7--
   8-- example documents
   9
  10doc1 = ( "Sesamstrasse"
  11       , scanText "Wieso, weshalb, warum? Wer nicht fragt, bleibt dumm!"
  12       )
  13
  14doc2 = ( "Kohl"
  15       , scanText "Wichtig ist, was am Ende hinten rauskommt."
  16       )
  17
  18doc3 = ( "Moeller"
  19       , scanText "Egal, ob Mailand oder Madrid, Hauptsache Italien! Italien, oder doch Spanien?"
  20       )
  21
  22doc4 = ( "Wurst"
  23       , scanText "Alles hat ein Ende, nur die Wurst hat zwei."
  24       )
  25
  26-- ------------------------------------------------------------
  27--
  28-- example index
  29
  30ix0     = emptyIndex
  31
  32ix1     = indexDocument doc1 ix0
  33ix12    = indexDocument doc2 ix1
  34ix123   = indexDocument doc3 ix12
  35ix1234  = indexDocument doc4 ix123
  36ix134   = deleteDocument (fst doc2) ix1234
  37ix34    = deleteDocument (fst doc1) ix134
  38
  39s1      = showIx ix1
  40s12     = showIx ix12
  41s1234   = showIx ix1234
  42s34     = showIx ix34
  43
  44-- ------------------------------------------------------------
weiter

weiter

ghc -e s1 IndexTest Index
weiter

weiter

ghc -e s12 IndexTest Index
weiter

weiter

ghc -e s1234 IndexTest Index
weiter

weiter

ghc -e s34 IndexTest Index
weiter

Letzte Änderung: 10.07.2012
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel