haskell हस्केल में हफ़्मण पेड़ से(पूर्व आदेश) बिटस्ट्रिंग का पुनर्निर्माण करना




recursion encoding (3)

मेरे पास निम्नलिखित हास्केल बहुरूपृत डेटा प्रकार हैं:

data Tree a = Leaf Int a | Node Int (Tree a) (Tree a)

पेड़ 0s और 1s के बिटस्ट्रिंग में संकुचित हो जाएगा ए '0' एक नोड का प्रतीक है और इसके बाद बाएं उप-रेखा के एन्कोडिंग का पालन किया जाता है, फिर दाएं उप-रेखा का एन्कोडिंग ए '1' एक पत्ता का प्रतीक है और इसके बाद 7 बीट जानकारी (उदाहरण के लिए यह एक चार हो सकता है)। प्रत्येक नोड / पत्ती को संग्रहीत जानकारी की आवृत्ति को भी माना जाता है, लेकिन इस समस्या के लिए यह महत्वपूर्ण नहीं है (इसलिए हम वहां कुछ भी डाल सकते हैं)।

उदाहरण के लिए, इस एन्कोडेड पेड़ से शुरू

[0,0,0,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,1,1,1,1,0,0,0,1,1,1,
 1,0,0,1,1,1,1,1,1,1,0,0,1,0,0,1,1,1,1,0,1,1,1,1,1,1,0,0,0,0,1]

यह इस तरह वापस कुछ देना माना जाता है

Node 0 (Node 0 (Node 0 (Leaf 0 'k') (Leaf 0 't')) 
       (Node 0 (Node 0 (Leaf 0 'q') (Leaf 0 'g')) (Leaf 0 'r'))) 
(Node 0 (Leaf 0 'w') (Leaf 0 'a'))

(रिक्त स्थान महत्वपूर्ण नहीं है, लेकिन यह एक पंक्ति पर फिट नहीं था)।

पेड़ के साथ मेरे पास बहुत कम अनुभव है, खासकर जब कोड को कार्यान्वित करते हैं मुझे इस बारे में एक अस्पष्ट विचार है कि मैं इस पर कागज पर कैसे हल करता हूं (गहराई / स्तर से निपटने के लिए एक स्टैक के समान कुछ का उपयोग करना), लेकिन मैं अभी भी थोड़ा खो रहा हूं।

किसी भी मदद या विचारों की सराहना कर रहे हैं!


ठीक है, आप बिट-स्ट्रीम से बाइट्स के पेड़ को पार्स करने की कोशिश कर रहे हैं। पार्सिंग उन मामलों में से एक है जहां यह कुछ संरचना स्थापित करने का भुगतान करता है: हम सफलता की एक सूची के द्वारा असफलता को कैसे बदलें की शैली में एक लघु पार्सर संयोजक पुस्तकालय लिखने जा रहे हैं, जो हमें एक मुहावरे में अपना कोड लिखने की अनुमति देगा कार्यात्मक शैली और मशीन के लिए बहुत काम का प्रतिनिधित्व करते हैं।

मदाद ट्रांसफार्मर की भाषा में पुरानी कविता का अनुवाद करना और "स्ट्रिंग" को "बिट स्ट्रिंग" के रूप में पढ़ना, हमारे पास

newtype Parser a = Parser (StateT [Bool] [] a)
    deriving (Functor, Applicative, Monad, Alternative)

runParser :: Parser a -> [Bool] -> [(a, [Bool])]
runParser (Parser m) = runStateT m

एक पार्सर एक मोनैडीक गणना है जो बूलियन की धारा पर स्टेटिया संचालित करता है, सफलतापूर्वक पार्स किए गए a का संग्रह प्रदान करता है। जीएचसी के GeneralizedNewtypeDeriving नवप्रवर्तन महाशक्तियों ने मुझे Monad एट अल के बॉयलरप्लेट उदाहरणों को दूर करने की इजाजत दी।

तो लक्ष्य, एक Parser (Tree SevenBits) - एक पार्सर जो Parser (Tree SevenBits) एक पेड़ देता है। (आप 7 बीट्स को Word8 में अपने Word8 में Tree लिए fmap इंस्टेंस fmap और fmap का उपयोग करके fmap ।) मैं Tree की निम्नलिखित परिभाषा का उपयोग करने जा रहा हूं क्योंकि यह आसान है - मुझे यकीन है कि आप यह समझ सकते हैं कि कैसे इस कोड को अपने खुद के अंत तक समायोजित करें

data Tree a = Leaf a | Node (Tree a) (Tree a) deriving Show

type SevenBits = (Bool, Bool, Bool, Bool, Bool, Bool, Bool)

यहां एक पार्सर है जो इनपुट स्ट्रीम से एक बिट का उपभोग करने का प्रयास करता है, यदि यह खाली है तो असफल हो रहा है:

one :: Parser Bool
one = Parser $ do
    stream <- get
    case stream of
        [] -> empty
        (x:xs) -> put xs *> return x

यहां वह एक है जो इनपुट स्ट्रीम से एक विशेष बिट का उपभोग करने का प्रयास करता है, यदि यह मेल नहीं खाता है तो विफल हो रहा है:

bit :: Bool -> Parser ()
bit b = do
    i <- one
    guard (i == b)

यहाँ मैं इनपुट बूँदों के अनुक्रम को डुप्लिकेट एम का उपयोग करके और एक ट्यूपल में पैकिंग के माध्यम से खींच रहा हूं। हम Leaf नोड्स की सामग्री को पॉप्युलेट करने के लिए इसका प्रयोग करेंगे।

sevenBits :: Parser SevenBits
sevenBits = pack7 <$> replicateM 7 one
    where pack7 [a,b,c,d,e,f,g] = (a, b, c, d, e, f, g)

अब हम आखिरकार उस कोड को लिख सकते हैं जो पेड़ संरचना को स्वयं पार्स करता है। हम <|> का उपयोग करके Node और Leaf विकल्पों के बीच चयन करेंगे।

tree :: Parser (Tree SevenBits)
tree = node <|> leaf
    where node = bit False *> liftA2 Node tree tree
          leaf = bit True *> fmap Leaf sevenBits

यदि node स्ट्रीम के सिर से कम बिट को पार्स करने में सफल हो जाता है, तो यह liftA2 साथ liftA2 कार्रवाइयों को liftA2 करके, सही liftA2 बाद बाईं उप-रेखा के एन्कोडिंग को बार-बार पार्स करना जारी liftA2 । चाल यह है कि node विफल हो जाता है अगर यह इनपुट स्ट्रीम के शीर्ष पर कम बिट का सामना नहीं करता है, जो <|> को node पर छोड़ने और इसके बजाय leaf प्रयास करने के लिए कहता है

ध्यान दें कि tree की संरचना, Tree प्रकार की संरचना को कैसे दर्शाती है। काम पर यह आवेदनकारी पार्सिंग है हम एकांतर से इस पार्सर को अनियंत्रित रूप से संरचित कर सकते हैं, पहले one का उपयोग करके one मनमाना बिट को पार्स करने के लिए और फिर यह निर्धारित करने के लिए कि क्या हमें पेड़ों की एक जोड़ी या पत्ती को पार्स करना जारी रखना चाहिए, उसके आधार पर case विश्लेषण का उपयोग करना। मेरी राय में यह संस्करण सरल, अधिक घोषणात्मक, और कम वर्बोस है।

साथ ही इस कोड की स्पष्टता को @ ब्रेज़ैड। नीरी के foldr आधारित समाधान की निम्न-स्तरीय शैली की तुलना करें। एक स्पष्ट परिमित-राज्य मशीन बनाने की बजाय जो नोड्स और पत्तियों को पार्स करने के बीच स्विच करता है - एक अनिवार्य-स्वाद वाला विचार - मेरा डिज़ाइन आपको liftA2 और <|> जैसे मानक कार्यों का उपयोग करके मशीन को व्याकरण का वर्णन करने देता है और विश्वास है कि पृथक्करण सही चीज़ करना।

वैसे भी, यहां मैं एक साधारण पेड़ को पार्स कर रहा हूं जिसमें पेपर की एक जोड़ी होती है (द्विआधारी-एन्कोडेड) संख्याएं 0 और 1 जैसा कि आप देख सकते हैं, यह एकल सफल पार्स और शेष बिट्स की एक खाली धारा देता है।

ghci> runParser tree $ map (>0) [0, 1, 0,0,0,0,0,0,0, 1, 0,0,0,0,0,0,1]
[(Node (Leaf (False, False, False, False, False, False, False)) (Leaf (False, False, False, False, False, False, True)),[])]

एक सही गुना करते हैं:

import Data.Char (chr)

data Tree a = Leaf a | Node (Tree a) (Tree a)
  deriving Show

build :: [Int] -> [Tree Char]
build xs = foldr go (\_ _ -> []) xs 0 0
  where
  nil = Leaf '?'
  go 0 run 0 0 = case run 0 0 of
    []     -> Node nil nil:[]
    x:[]   -> Node x   nil:[]
    x:y:zs -> Node x   y  :zs

  go 1 run 0 0 = run 0 1
  go _ _   _ 0 = error "this should not happen!"
  go x run v 7 = (Leaf $ chr (v * 2 + x)): run 0 0
  go x run v k = run (v * 2 + x) (k + 1)

फिर:

\> head $ build [0,0,0,1,1,1,0, ...] -- the list of 01s as in the question
Node (Node (Node (Leaf 'k') (Leaf 't'))
      (Node (Node (Leaf 'q') (Leaf 'g')) (Leaf 'r')))
 (Node (Leaf 'w') (Leaf 'a'))

ठीक है, यहां एक सरल (एड-हॉक, लेकिन समझने में आसान) तरीका है।

निम्नलिखित प्रकार के साथ हमें फ़ंक्शन parse को बुलाए जाने की आवश्यकता है:

parse  :: [Int] -> Tree Char

ढेर के साथ आपने जिस दृष्टिकोण का उल्लेख किया, वह जरूरी है यहां हम पुनरावर्ती कॉलों पर बस रखते हैं स्टैक कंपाइलर द्वारा बनाया जाएगा और इसमें प्रत्येक रिकर्सिव कॉल को संग्रहीत किया जाएगा (कम से कम आप इसे इस तरह सोच सकते हैं, यदि आप चाहते हैं, या सिर्फ यह सब पैराग्राफ को अनदेखा कर)।

तो, यह विचार निम्न है: जब भी आपको 0 मिलते हैं, आपको एल्गोरिदम को दो पुनरावर्ती कॉल करने की आवश्यकता होती है। पहली पुनरावर्ती कॉल पेड़ की एक शाखा (बाएं एक) पढ़ी जाएगी। दूसरे को तर्क के रूप में शेष सूची के साथ बुलाया जाना चाहिए। बाकी पहले रिकर्सिव कॉल द्वारा छोड़ा गया। इसलिए, हमें निम्नलिखित प्रकार के साथ एक एक्जिकिक फ़ंक्शन parse' ज़रूरत है (अब हम एक जोड़ी वापस लौटते हैं, शेष सूची में दूसरा मान):

parse' :: [Int] -> (Tree Char, [Int])

इसके बाद, आप कोड का एक टुकड़ा देख सकते हैं जहां पहले 0 जैसा वर्णित है।
1 मामले के लिए, हमें अगले 7 नंबरों को लेना होगा और उन्हें किसी भी तरह से toChar में toChar (मैं आपके लिए toChar की परिभाषा छोड़ देता हूं), फिर, केवल एक Leaf और बाकी की सूची वापस करें

parse' (0:xs) = let (l, xs')    = parse' xs
                    (r, xs'')   = parse' xs' in (Node 0 l r, xs'') --xs'' should be []
parse' (1:xs) = let w = toChar (take 7 xs) in (Leaf 0 w , drop 7 xs)

अंत में, हमारा पार्स फ़ंक्शन केवल सहायक पार्स को कॉल करता है और जोड़ी का पहला तत्व देता है।

parse xs = fst $ parse' xs