הפעולה key in dict

הפעולה key in dict

Gal (guest) 28 Jan 2016 13:29

שלום,

יש לי שתי שאלות:
1.
כאשר יש לי מילון, d,
ואני רוצה לדעת אם המפתח
key
מוכל בו, אני אשתמש בפעולה הבאה:
key in d
פעולה זו שקולה לפעולה
d.get(key) != None
ולכן היעילות שלה היא O(1), נכון?
(בהנחה שזמן חישוב ההאש של המפתח הוא קבוע)

2. אוכל לקבל שוב הסבר על איזה מהדחיסות, למפל-זיו או האפמן יותר יעילה ולמה במקרים הבאים:
א. טקסט אקראי לחלוטין
[[/div]]

ב. טקסט מתוך עיתון
ג. הטקסט מההרצאות של כולרה

תודה מראש!

Re: הפעולה key in dict

Amir Rubinstein 29 Jan 2016 07:17

Re your first question, yes, it is O(1), but on average, not worst case.

Re your second one, continuing Netanel's reply: first - I suggest running the code and observing the results. Generally, a random text is expected to have a uniform distribution of characters, thus Huffman will not compress it (assuming the random text contains the 128 ascii chars, otherwise it's not a fair comparison). although the random text is not likely to have long repeats, LZ will still compress some repetitions, albeit short. Newspapers (i.e. natural, human spoken) languages are much more repetitive. You cannot tell in advance which of Huffman or LZ will do better, it depends how repetitive it is indeed. The same for biological sequences.

Netanel (guest) 28 Jan 2016 15:35

when we talk about huffman compression, it really depends on whether corpus is the text it self. if so, i think huffman will preform better, but then is the text really random? if we are talking about a rondom text given a specific corpus, i think LZ will preform better because the info we gained from the corpus is irrelevant for our random text.