Как удалить слово из структуры Trie? - PullRequest
Новая
       42

Как удалить слово из структуры Trie?

1 голос
/ 03 апреля 2011

возможно, я не достаточно умен, чтобы учить Хаскелла, но я бы дал ему последний шанс.Я застрял в реализации удаления записи из дерева, Trie, как структура, чтобы быть более конкретной (http://en.wikipedia.org/wiki/Trie).

Я ищу любые советы (не решение!), Как реализовать такой чистыйЯ имел представление об одном алгоритме. Воссоздайте новое дерево путем обхода всего дерева, «пропуская» значения, равные каждому символу слова, с условием ребра, возвращающим исходное дерево, если следующий символ не будет найден. Но возникаетпроблема, когда символ также принадлежит другому слову. 

data Trie = Trie { commonness :: Maybe Int
                 , children :: [(Char, Trie)]
                 } deriving (Eq, Read, Show)

-- Creates an empty "dictionary"
trie :: Trie
trie = Trie { commonness = Nothing, children = [] }

-- Inserts a word with given commonness into dictionary
add :: String -> Int -> Trie -> Trie
add [] freq tree
    | (0 <= freq) && (freq <= 16) = tree { commonness = Just freq }
    | otherwise = error $ "Commonness out of bounds: " ++ (show freq)
add word freq tree = tree { children = traverse word (children tree) }
    where
        traverse [] tree = error $ "traverse called with [] " ++ (show tree)
        traverse (x:xs) [] = [(x, add xs freq trie)]
        traverse str@(x:xs) (t:ts)
            | x == fst t = (x, add xs freq $ snd t):ts
            | otherwise = t:(traverse str ts)

remove :: String -> Trie -> Trie
???

И данные выглядят так: 

GHCi> putStrLn $ groom $ add "learn" 16 $ add "leap" 5 $ add "sing" 7 $ add "lift" 10 trie

Trie{commonness = Nothing,
     children =
       [('l',
         Trie{commonness = Nothing,
              children =
                [('i',
                  Trie{commonness = Nothing,
                       children =
                         [('f',
                           Trie{commonness = Nothing,
                                children = [('t', Trie{commonness = Just 10, children = []})]})]}),
                 ('e',
                  Trie{commonness = Nothing,
                       children =
                         [('a',
                           Trie{commonness = Nothing,
                                children =
                                  [('p', Trie{commonness = Just 5, children = []}),
                                   ('r',
                                    Trie{commonness = Nothing,
                                         children =
                                           [('n',
                                             Trie{commonness = Just 16, children = []})]})]})]})]}),
        ('s',
         Trie{commonness = Nothing,
              children =
                [('i',
                  Trie{commonness = Nothing,
                       children =
                         [('n',
                           Trie{commonness = Nothing,
                                children =
                                  [('g', Trie{commonness = Just 7, children = []})]})]})]})]}

Ответы [ 2 ]

4 голосов
/ 04 апреля 2011

Это будет проще, если вы используете Map Char Trie вместо [(Char,Trie)] для своего дочернего стола.Вот что я собираюсь предположить для этого ответа.Я начну с индуктивного кейса: 

import qualified Data.Map as Map

remove :: String -> Trie -> Trie
remove (c:cs) t = t { children = Map.alter remove' c (children t) }
    where
    remove' (Just t) = Just (remove cs t)
    remove' Nothing = Nothing
remove [] t = ...

Я оставлю базовый кейс для вас.Вот документы для функции Map, которую я использовал, alter .Вы можете получить это же решение без использования Map, если вы внедрили alter для [(Char,a)].

Упражнение: remove' довольно многословно.Посмотрите, сможете ли вы сократить его, используя fmap.

0 голосов
/ 23 сентября 2018

В Python вы можете сделать что-то вроде этого 

def remove_string_helper(self, string, pnode, index):
    if pnode:
        flag = False
        if index < len(string):
            flag = self.remove_string_helper(string, pnode.childs.get(string[index]), index + 1)

        if index == len(string) and pnode.is_complete_word:
            pnode.is_complete_word = False
            return len(pnode.childs) == 0

        if flag:
            pnode.childs.pop(string[index])
            return len(self.childs) == 0

    return False

def remove_string(self, string):
    self.remove_string_helper(string, self.childs.get(string[0]), 1)
...