पाइथन शब्दकोशों के लिए मेमोरी कुशल विकल्प

Question

मेरी वर्तमान साइड परियोजनाओं में से एक में, मैं शब्द ट्रिपलेट की आवृत्ति को देखते हुए कुछ पाठ के माध्यम से स्कैन कर रहा हूं। मेरे पहले में, मैंने डिफ़ॉल्ट शब्दकोश का उपयोग तीन स्तरों को गहराई से किया था। दूसरे शब्दों में, topDict[word1][word2][word3] रिटर्न समय की संख्या इन शब्दों पाठ में दिखाई देते हैं, topDict[word1][word2]

यह कार्यों सभी शब्दों की सही, आदि है कि 1 शब्द और 2 निम्नलिखित दिखाई दिया के साथ एक शब्दकोश देता है, लेकिन यह बहुत अच्छी मेमोरी की है। मेरे प्रारंभिक परीक्षणों में यह टेक्स्ट फ़ाइल में ट्रिपलेट्स को संग्रहीत करने की स्मृति की 20 गुणा की तरह कुछ उपयोग करता था, जो कि स्मृति ओवरहेड की अत्यधिक मात्रा में लगता है।

मेरा संदेह यह है कि इनमें से कई शब्दकोश वास्तव में उपयोग किए जाने वाले कई स्लॉट के साथ बनाए जा रहे हैं, इसलिए मैं शब्दकोशों को किसी अन्य चीज़ से बदलना चाहता हूं जो इस तरह से उपयोग किए जाने पर अधिक मेमोरी कुशल है। मैं दृढ़ता से एक समाधान पसंद करूंगा जो शब्दकोशों की रेखाओं के साथ मुख्य लुकअप की अनुमति देता है।

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

तो, क्या किसी के पास मेरे लिए कोई सुझाव है? जोड़ने

संपादित करने के लिए:

धन्यवाद प्रतिक्रिया के लिए अब तक। अब तक के कुछ उत्तरों ने टुपल्स का उपयोग करने का सुझाव दिया है, जो वास्तव में मेरे लिए बहुत कुछ नहीं करता था जब मैंने पहले दो शब्दों को टुपल में घनत्व दिया था। मैं तीनों को एक कुंजी के रूप में उपयोग करने में संकोच कर रहा हूं क्योंकि मैं चाहता हूं कि पहले दो दिए गए सभी तीसरे शब्दों को देखना आसान हो। (यानी मुझे topDict[word1, word2].keys() के परिणाम की तरह कुछ चाहिए)।

वर्तमान डेटासेट जो मैं खेल रहा हूं वह Wikipedia For Schools का नवीनतम संस्करण है। उदाहरण के लिए, पहले हजार पृष्ठों को पार्स करने के नतीजे एक टेक्स्ट फ़ाइल के लिए 11 एमबी की तरह हैं, जहां प्रत्येक पंक्ति तीन शब्द है और सभी टैब अलग-अलग हैं। शब्दकोश प्रारूप में पाठ को संग्रहीत करना अब मैं 185 एमबी का उपयोग कर रहा हूं। मुझे पता है कि पॉइंटर्स और व्हाट्नॉट के लिए कुछ अतिरिक्त ओवरहेड होगा, लेकिन अंतर अत्यधिक लगता है।

Answer 1

कुछ माप। मैंने 24 एमबी फ़ाइल का उत्पादन करने वाले 10 एमबी मुफ्त ई-बुक टेक्स्ट और गणना ट्रिगर आवृत्तियों को लिया। इसे विभिन्न सरल पायथन डेटा संरचनाओं में संग्रहीत करने से केबी में यह बहुत अधिक जगह ले ली गई, आरएसएस को पीएस चलाने से मापा जाता है, जहां डी एक dict, कुंजी और freqs सूचियां हैं, और ए, बी, सी, freq ट्रिगर रिकॉर्ड के क्षेत्र हैं:

295760  S. Lott's answer 
237984  S. Lott's with keys interned before passing in 
203172 [*] d[(a,b,c)] = int(freq) 
203156  d[a][b][c] = int(freq) 
189132  keys.append((a,b,c)); freqs.append(int(freq)) 
146132  d[intern(a),intern(b)][intern(c)] = int(freq) 
145408  d[intern(a)][intern(b)][intern(c)] = int(freq) 
83888 [*] d[a+' '+b+' '+c] = int(freq) 
82776 [*] d[(intern(a),intern(b),intern(c))] = int(freq) 
68756  keys.append((intern(a),intern(b),intern(c))); freqs.append(int(freq)) 
60320  keys.append(a+' '+b+' '+c); freqs.append(int(freq)) 
50556  pair array 
48320  squeezed pair array 
33024  squeezed single array 

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

'जोयर सरणी' मेरे मूल उत्तर में नीचे दी गई योजना है ("मैं सरणी से शुरू करूंगा कुंजी पहले दो शब्द होने के नाते ... "), जहां प्रत्येक जोड़ी के लिए मान तालिका एक स्ट्रिंग के रूप में दर्शायी जाती है। 'निचोड़ा जोड़ी सरणी' वही है, आवृत्ति मान को छोड़कर जो 1 के बराबर है (सबसे आम केस)। 'निचोड़ एकल सरणी' निचोड़ा जोड़ी सरणी की तरह है, लेकिन एक स्ट्रिंग (एक विभाजक चरित्र के साथ) के रूप में ग्लोम्स कुंजी और मूल्य एक साथ। निचोड़ा एकल सरणी कोड:

import collections 

def build(file): 
    pairs = collections.defaultdict(list) 
    for line in file: # N.B. file assumed to be already sorted 
     a, b, c, freq = line.split() 
     key = ' '.join((a, b)) 
     pairs[key].append(c + ':' + freq if freq != '1' else c) 
    out = open('squeezedsinglearrayfile', 'w') 
    for key in sorted(pairs.keys()): 
     out.write('%s|%s\n' % (key, ' '.join(pairs[key]))) 

def load(): 
    return open('squeezedsinglearrayfile').readlines() 

if __name__ == '__main__': 
    build(open('freqs')) 

मैं इस संरचना से मूल्यों को देखने के लिए कोड लिखा गया (उपयोग करते हैं, द्विभाजित नीचे वर्णित के रूप में), सजावटी संकुचित स्वरुप भी नीचे वर्णित लागू किया है।

मूल उत्तर: तारों की एक सरल क्रमबद्ध सरणी, प्रत्येक स्ट्रिंग शब्दों का अंतरिक्ष-पृथक संगतता है, जो बिसेक्ट मॉड्यूल का उपयोग करके खोजी जाती है, शुरुआत के लिए प्रयास करने योग्य होनी चाहिए। यह पॉइंटर्स, आदि पर स्थान बचाता है। यह अभी भी शब्दों की पुनरावृत्ति के कारण अंतरिक्ष को बर्बाद कर देता है; सामान्य उपसर्गों को बाहर निकालने के लिए एक मानक चाल है, जिसमें उन्हें वापस लाने के लिए सूचकांक का एक और स्तर है, लेकिन यह अधिक जटिल और धीमा है। (विचार एक संपीड़ित रूप में सरणी के लगातार भाग को संग्रहीत करना है जिसे अनुक्रमिक रूप से स्कैन किया जाना चाहिए, प्रत्येक खंड में यादृच्छिक-पहुंच अनुक्रमणिका के साथ। भाग संकुचित करने के लिए काफी बड़े हैं, लेकिन उचित पहुंच समय के लिए पर्याप्त छोटे हैं। विशेष संपीड़न योजना यहां लागू है: यदि लगातार प्रविष्टियां 'हैलो जॉर्ज' और 'हैलो वर्ल्ड' हैं, तो दूसरी प्रविष्टि को '6world' बनें। (6 सामान्य में उपसर्ग की लंबाई है।) या शायद आप zlib का उपयोग कर दूर हो सकते हैं? वैसे भी, आप पूर्ण-पाठ खोज में उपयोग की जाने वाली शब्दकोश संरचनाओं को देखकर इस नस में और अधिक जानकारी प्राप्त कर सकते हैं।) इसलिए, विशेष रूप से, मैं सरणी के साथ शुरू करूंगा जिसमें कुंजियां पहले दो शब्द होंगी, समानांतर सरणी के साथ जिनकी प्रविष्टियां संभव हो सकती हैं तीसरे शब्द और उनकी आवृत्तियों। यह अभी भी चूस सकता है, हालांकि - मुझे लगता है कि आप भाग्य से बाहर हो सकते हैं जहां तक ​​बैटरी-मेमोरी-कुशल विकल्प शामिल हैं।

इसके अलावा, बाइनरी पेड़ संरचना मेमोरी दक्षता के लिए अनुशंसित नहीं है। उदा।, this paper इसी तरह की समस्या पर विभिन्न डेटा संरचनाओं का परीक्षण करता है (यद्यपि ट्रिग्राम के बजाए यूनिग्राम) और उस माप से सभी वृक्ष संरचनाओं को हरा करने के लिए हैशटेबल पाता है।

मुझे किसी अन्य व्यक्ति के रूप में उल्लेख किया जाना चाहिए था, कि क्रमबद्ध सरणी केवल शब्दसूची के लिए उपयोग की जा सकती है, न कि बिग्राम या ट्रिग्राम; फिर आपके 'वास्तविक' डेटा संरचना के लिए, जो भी हो, आप स्ट्रिंग्स के बजाय पूर्णांक कुंजी का उपयोग करें - शब्दसूची में सूचकांक। (लेकिन यह आपको शब्द सूची में छोड़कर सामान्य उपसर्गों का शोषण करने से रोकता है। शायद मुझे यह सब सुझाव नहीं देना चाहिए।)

Answer 2

आप एक ही शब्दकोश का उपयोग करने की कोशिश कर सकते हैं, केवल एक स्तर गहरा।

topDictionary[word1+delimiter+word2+delimiter+word3] 

डेलीमीटर सादा "" हो सकता है। (या उपयोग (शब्द 1, शब्द 2, शब्द 3))

यह लागू करना सबसे आसान होगा। मेरा मानना ​​है कि आप एक छोटे से सुधार देखेंगे, अगर यह काफी नहीं है ... ... मैं कुछ के बारे में सोच होगा ...

Answer 3

एक जोड़े प्रयास:

मैं समझ आप कुछ कर रहे इसके समान:

from __future__ import with_statement 

import time 
from collections import deque, defaultdict 

# Just used to generate some triples of words 
def triplegen(words="/usr/share/dict/words"): 
    d=deque() 
    with open(words) as f: 
     for i in range(3): 
      d.append(f.readline().strip()) 

     while d[-1] != '': 
      yield tuple(d) 
      d.popleft() 
      d.append(f.readline().strip()) 

if __name__ == '__main__': 
    class D(dict): 
     def __missing__(self, key): 
      self[key] = D() 
      return self[key] 
    h=D() 
    for a, b, c in triplegen(): 
     h[a][b][c] = 1 
    time.sleep(60) 

यह मुझे ~ 88MB देता है।

भंडारण बदलने

को

h[a, b, c] = 1 

लेता है ~ 25 एमबी

होना शामिल ए, बी, और सी यह 31MB के बारे में लेने के लिए बनाता है। मेरा मामला थोड़ा खास है क्योंकि मेरे शब्द इनपुट पर कभी दोहराए नहीं जाते हैं। आप स्वयं कुछ बदलावों को आजमा सकते हैं और देख सकते हैं कि इनमें से कोई आपकी मदद करता है या नहीं।

Answer 4

आप सभी शब्दों को एक शब्दकोश में डाल सकते हैं। कुंजी शब्द होगी, और मान संख्या (अनुक्रमणिका) है। indexDict में साथ

Word1=indexDict[word1] 
Word2=indexDict[word2] 
Word3=indexDict[word3] 

topDictionary[Word1][Word2][Word3] 

सम्मिलित:

if word not in indexDict: 
    indexDict[word]=len(indexDict) 

Answer 5

उपयोग tuples

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

d = {} 
d[ word1, word2, word3 ] = 1 

इसके अलावा एक प्लस के रूप में, आप defaultdict

• इस्तेमाल कर सकते हैं ताकि तत्वों प्रविष्टियों की जरूरत नहीं है कि हमेशा लौट 0
• और इतना है कि यू d[w1,w2,w3] += 1 कह सकते हैं की जाँच के बिना यदि कुंजी पहले मौजूद है या नहीं

उदाहरण:

from collections import defaultdict 
d = defaultdict(int) 
d["first","word","tuple"] += 1 

आप सूची समझ

का उपयोग करके सभी शब्द "word3" है कि (word1, WORD2) के साथ tupled कर रहे हैं तो dictionary.keys में इसके लिए खोज() को खोजने के लिए की जरूरत है अगर आप एक टपल है, टी, तो आप प्राप्त कर सकते हैं पहले दो आइटम स्लाइस का उपयोग कर:

>>> a = (1,2,3) 
>>> a[:2] 
(1, 2) 

सूची comprehensions साथ tuples खोज के लिए एक छोटा सा उदाहरण:

>>> b = [(1,2,3),(1,2,5),(3,4,6)] 
>>> search = (1,2) 
>>> [a[2] for a in b if a[:2] == search] 
[3, 5] 

आप यहाँ देख, हम सभी वस्तुओं है कि में तीसरे आइटम के रूप में दिखाई देते हैं की एक सूची मिल गया उस पर tuples के साथ शुरू करें (1,2)

Answer 6

ठीक है, तो आप मूल रूप से एक दुर्लभ 3 डी स्पेस को स्टोर करने की कोशिश कर रहे हैं। एल्गोरिदम और डेटा संरचना की पसंद के लिए आप इस स्थान पर पहुंचने वाले एक्सेस पैटर्न के लिए महत्वपूर्ण हैं। अपने डेटा स्रोत को ध्यान में रखते हुए, क्या आप इसे ग्रिड में खिलाना चाहते हैं? यदि आपको ओ (1) एक्सेस की आवश्यकता नहीं है:

मेमोरी दक्षता प्राप्त करने के लिए आप उस स्थान को समान संख्या में प्रविष्टियों के साथ उप-स्थान में विभाजित करना चाहते हैं। (एक बीटी की तरह)। तो के साथ एक डेटा संरचना:

• firstWordRange
• secondWordRange
• thirdWordRange
• numberOfEntries
• प्रविष्टियों की एक हल कर ब्लॉक।
• सभी 3 आयामों

Answer 7

इस मामले में में अगले और पिछले ब्लॉक, ZODB ¹ BTrees उपयोगी हो सकता है, क्योंकि वे बहुत कम स्मृति के भूखे हैं। BTrees.OOBtree (ऑब्जेक्ट वैल्यू के ऑब्जेक्ट कुंजियों) या BTrees.OIBTree (ऑब्जेक्ट कुंजियों के लिए ऑब्जेक्ट कुंजी) का उपयोग करें, और अपनी कुंजी के रूप में 3-शब्द tuples का उपयोग करें।

कुछ की तरह:

from BTrees.OOBTree import OOBTree as BTree 

इंटरफेस है, और अधिक या कम, dict की तरह, अतिरिक्त बोनस (आप के लिए) है कि .keys, .items, .iterkeys और .iteritems दो min, max वैकल्पिक तर्क के साथ:

>>> t=BTree() 
>>> t['a', 'b', 'c']= 10 
>>> t['a', 'b', 'z']= 11 
>>> t['a', 'a', 'z']= 12 
>>> t['a', 'd', 'z']= 13 
>>> print list(t.keys(('a', 'b'), ('a', 'c'))) 
[('a', 'b', 'c'), ('a', 'b', 'z')] 

¹ ध्यान दें कि यदि आप विंडोज़ पर हैं और पाइथन> 2.4 के साथ काम करते हैं, तो मुझे पता है कि हाल के पाइथन संस्करणों के लिए पैकेज हैं, लेकिन मैं कहां याद नहीं कर सकता।

पुनश्च वे CheeseShop ☺

Answer 8

आप को लागू करने हैं Markovian पाठ पीढ़ी में मौजूद हैं?

यदि आपकी श्रृंखला तीसरे की संभावनाओं के लिए 2 शब्द मैप करती है तो मैं 3-शब्द हिस्टोग्राम में एक शब्दकोश मैपिंग के-टुपल्स का उपयोग करता हूं। हिस्टोग्राम को लागू करने के लिए एक छोटा (लेकिन स्मृति-भूखा) तरीका दोहराने वाली सूची का उपयोग करना होगा, और फिर random.choice आपको उचित संभावना के साथ एक शब्द देता है।

यहाँ एक पैरामीटर के रूप में कश्मीर टपल साथ एक कार्यान्वयन है:

import random 

# can change these functions to use a dict-based histogram 
# instead of a list with repeats 
def default_histogram():   return [] 
def add_to_histogram(item, hist): hist.append(item) 
def choose_from_histogram(hist): return random.choice(hist) 

K=2 # look 2 words back 
words = ... 
d = {} 

# build histograms 
for i in xrange(len(words)-K-1): 
    key = words[i:i+K] 
    word = words[i+K] 

    d.setdefault(key, default_histogram()) 
    add_to_histogram(word, d[key]) 

# generate text 
start = random.randrange(len(words)-K-1) 
key = words[start:start+K] 
for i in NUM_WORDS_TO_GENERATE: 
    word = choose_from_histogram(d[key]) 
    print word, 
    key = key[1:] + (word,) 

Answer 9

तो स्मृति बस काफी बड़ा नहीं है, pybsddb मदद कर सकते हैं एक डिस्क के लगातार मानचित्र की दुकान।

Answer 10

आप एक numpy multidimensional सरणी का उपयोग कर सकते हैं। आपको सरणी में अनुक्रमित करने के लिए स्ट्रिंग्स की बजाय संख्याओं का उपयोग करने की आवश्यकता होगी, लेकिन इसे संख्याओं को शब्दों को मैप करने के लिए एक एकल dict का उपयोग करके हल किया जा सकता है।

import numpy 
w = {'word1':1, 'word2':2, 'word3':3, 'word4':4} 
a = numpy.zeros((4,4,4)) 

फिर अपने सरणी में सूचकांक के लिए, आप की तरह कुछ करना चाहते हैं:

a[w[word1], w[word2], w[word3]] += 1 

वाक्य रचना सुंदर नहीं है यही कारण है, लेकिन NumPy सरणी के बारे में के रूप में कुशल के रूप में कुछ भी आप पाते हैं होने की संभावना हो रहे हैं। ध्यान दें कि मैंने इस कोड को आजमाया नहीं है, इसलिए मैं कुछ विवरणों में बंद हो सकता हूं। बस यहाँ स्मृति से जा रहा है।

Answer 11

यहां एक वृक्ष संरचना है जो शब्दों की क्रमबद्ध सूची बनाए रखने के लिए बिसेक्ट लाइब्रेरी का उपयोग करती है। ओ (लॉग 2 (एन)) में प्रत्येक लुकअप।

import bisect 

class WordList(object): 
    """Leaf-level is list of words and counts.""" 
    def __init__(self): 
     self.words= [ ('\xff-None-',0) ] 
    def count(self, wordTuple): 
     assert len(wordTuple)==1 
     word= wordTuple[0] 
     loc= bisect.bisect_left(self.words, word) 
     if self.words[loc][0] != word: 
      self.words.insert(loc, (word,0))   
     self.words[loc]= (word, self.words[loc][1]+1) 
    def getWords(self): 
     return self.words[:-1] 

class WordTree(object): 
    """Above non-leaf nodes are words and either trees or lists.""" 
    def __init__(self): 
     self.words= [ ('\xff-None-',None) ] 
    def count(self, wordTuple): 
     head, tail = wordTuple[0], wordTuple[1:] 
     loc= bisect.bisect_left(self.words, head) 
     if self.words[loc][0] != head: 
      if len(tail) == 1: 
       newList= WordList() 
      else: 
       newList= WordTree() 
      self.words.insert(loc, (head,newList)) 
     self.words[loc][1].count(tail) 
    def getWords(self): 
     return self.words[:-1] 

t = WordTree() 
for a in (('the','quick','brown'), ('the','quick','fox')): 
    t.count(a) 

for w1,wt1 in t.getWords(): 
    print w1 
    for w2,wt2 in wt1.getWords(): 
     print " ", w2 
     for w3 in wt2.getWords(): 
      print " ", w3 

सादगी के लिए, यह प्रत्येक पेड़ और सूची में एक डमी मूल्य का उपयोग करता है। यह अंतहीन अगर-बयानों को निर्धारित करता है कि यह तुलना करने से पहले सूची वास्तव में खाली थी या नहीं। यह केवल एक बार खाली है, इसलिए if-statement सभी n -1 अन्य शब्दों के लिए बर्बाद हो जाते हैं।

Answer 12

SciPy विरल मैट्रिक्स है, तो आप पहले दो शब्द एक टपल कर सकते हैं, तो आप कुछ इस तरह कर सकते हैं:

import numpy as N 
from scipy import sparse 

word_index = {} 
count = sparse.lil_matrix((word_count*word_count, word_count), dtype=N.int) 

for word1, word2, word3 in triple_list: 
    w1 = word_index.setdefault(word1, len(word_index)) 
    w2 = word_index.setdefault(word2, len(word_index)) 
    w3 = word_index.setdefault(word3, len(word_index)) 
    w1_w2 = w1 * word_count + w2 
    count[w1_w2,w3] += 1