6
ठीक है, तो, कहें कि मेरे पास एक टेक्स्ट फ़ाइल है (आवश्यक रूप से प्रत्येक संभावित प्रतीक नहीं है) और मैं आवृत्ति की गणना करने के बाद, प्रत्येक प्रतीक की आवृत्ति की गणना करना चाहता हूं, फिर मुझे प्रत्येक प्रतीक और इसकी आवृत्ति से पहुंचने की आवश्यकता है सबसे कम से कम लगातार। प्रतीकों अनिवार्य रूप से ASCII वर्ण नहीं हैं, वे सभी समान लंबाई के बावजूद मनमानी बाइट अनुक्रम हो सकते हैं।क्या फ़ाइल में सभी प्रतीकों की आवृत्ति की गणना करने का कोई बेहतर तरीका है?
मैं कुछ इस तरह (स्यूडोकोड में) कर रहा विचार कर रहा था:
function add_to_heap (symbol)
freq = heap.find(symbol).frequency
if (freq.exists? == true)
freq++
else
symbol.freq = 1
heap.insert(symbol)
MaxBinaryHeap heap
while somefile != EOF
symbol = read_byte(somefile)
heap.add_to_heap(symbol)
heap.sort_by_frequency()
while heap.root != empty
root = heap.extract_root()
do_stuff(root)
मैं सोच रहा था: वहाँ एक बेहतर, सरल गणना करने के लिए जिस तरह से और दुकान कितनी बार प्रत्येक प्रतीक एक फ़ाइल में होता है?
लगता है कि आपके पास दो विकल्प हैं, हैशप आपको ओ (1) आवृत्ति पुनर्प्राप्ति दे रहा है लेकिन कोई आदेश नहीं दिया गया है (अक्सर कम से कम लगातार) परिणाम या ओ (एलजी एन) खोज पेड़/ढेर का उपयोग करके डालें और खोज करें लेकिन आपको ऑर्डर देने वाला अक्सर कम से कम लगातार) परिणाम। –
एक द्विआधारी ढेर इस के लिए विशेष रूप से अच्छी डेटा संरचना नहीं है, क्योंकि ढेर में मनमाने ढंग से नोड ढूंढना महंगा है। आप बाइनरी पेड़ के साथ बेहतर काम करेंगे या, जैसा कि दूसरों ने इंगित किया है, किसी प्रकार की हैश टेबल। –