User talk:Jarek Duda

From Wikipedia, the free encyclopedia

1 Asymmetric binary system
2 Asymmetric binary system must be reconsidered for publication
3 AfD nomination of Chiral life concept
4 It looks like you have been here a few months but you never got the token "Welcome" message so:
5 AfD nomination of Asymmetric binary system
6 Asymmetric binary systems
7 Data compression
8 General case
9 See also
10 References
11 External links

[edit] Asymmetric binary system

I was surprised to see your first article here, as I had come across your contribution at arxiv.org only a few days ago (in my effort to keep current with all Huffman-related papers). Unfortunately, I don't think this should be a Wikipedia article at this point, due to issues outlined in WP:RS#Self-published_sources, WP:SPS, and WP:N. (There is or was another policy or guideline arguing against citing one's own sources, but either I can't find it or it changed.) Basically, this topic hasn't been published in a reliable primary source, let alone a secondary source. (Reliability isn't about whether you are right or wrong, but rather about whether some level of social verification has occurred.) It comes very close to going against the spirit of Wikipedia:Wikipedia is not for things made up in school one day#The right way to get things you or your friends made up into Wikipedia, although naturally your research is at a far more advanced level than this. If you'd like to get rid of it, you can use WP:PROD to do so painlessly. If not, please provide published sources; although I really doubt that it should be its own article at this point in time, if you believe it should be, it should be brought up to snuff in terms of external citations. If this doesn't happen, someone else is liable to see the article and try to delete it via WP:AfD. Calbaer 18:18, 11 November 2007 (UTC)

[edit] Asymmetric binary system must be reconsidered for publication

I remember this first article. It did not explain concept clearly and that was the main reason for deletion of the article not because it was new and never mentioned in other sources. But times change. Now there are several successful implementations and explanations of the method that can be found via search engines. It is shown that hybrid of Huffman and ABS coding can give the encoding/decoding speed higher than in best range encoders with the same compression ratio. I believe that ABS should not be left out of scope of Wikipedia. Andrew Polar. April 09, 2008. —Preceding unsigned comment added by 63.144.61.175 (talk) 14:23, 9 April 2008 (UTC)

[edit] AfD nomination of Chiral life concept

I have nominated Chiral life concept, an article you created, for deletion. I do not feel that this article satisfies Wikipedia's criteria for inclusion, and have explained why at Wikipedia:Articles for deletion/Chiral life concept. Your opinions on the matter are welcome at that same discussion page; also, you are welcome to edit the article to address these concerns. Thank you for your time. Dougie WII (talk) 12:00, 13 December 2007 (UTC)

[edit] It looks like you have been here a few months but you never got the token "Welcome" message so:

Welcome!

Hello, Jarek Duda, and welcome to Wikipedia! Thank you for your contributions. I hope you like the place and decide to stay. Here are some pages that you might find helpful:

I hope you enjoy editing here and being a Wikipedian! Please sign your messages on discussion pages using four tildes (~~~~); this will automatically insert your username and the date. If you need help, check out Wikipedia:Questions, ask me on my talk page, or ask your question on this page and then place {{helpme}} before the question. Again, welcome! -Gtstricky^{Talk or C} 19:21, 14 December 2007 (UTC)

[edit] AfD nomination of Asymmetric binary system

I have nominated Asymmetric binary system, an article you created, for deletion. I do not feel that this article satisfies Wikipedia's criteria for inclusion, and have explained why at Wikipedia:Articles for deletion/Asymmetric binary system. Your opinions on the matter are welcome at that same discussion page; also, you are welcome to edit the article to address these concerns. Thank you for your time. Dougie WII (talk) 12:42, 16 December 2007 (UTC)

I deleted the page "Asymmetric numeral systems" that you created, because it's on the same topic and the community decided that it is not fit for Wikipedia. -- Jitse Niesen (talk) 12:36, 1 April 2008 (UTC)

If someone needs - for now I'm placing here the deleted article. Feel free to correct it.

The asymmetric numeral system is generalization of numeral system which are optimal to encode sequence of digits which has equal probability. In asymmetric case we can freely manipulate this probability distribution.

[edit] Asymmetric binary systems

In the binary system, when we have some information stored in a natural number $x'$ and we want to insert there information stored in a binary digit $b$ , we can put it ont the least important position:

$x=code_{1/2}(b,x'):=2\cdot x'+b$ .

Now having $x$ we can easily restore x', $d$

$(b,x')=decode_{1/2}(x):=(x \mod 2,\lfloor x/2 \rfloor)$

So these operations are reverses of each other.

We can generalize it to any probability distribution, denote $q\in(0,1)$ - probability of '1'

$code_q(0,x'):=\lfloor \frac{x'}{1-q}\rfloor$

$code_q(1,x'):=\lceil \frac{x'+1}{q} \rceil-1$

$d e c o d e q (x): = (b, x b)$

where

$b=\lfloor((x+1)q)\rfloor-\lfloor(xq)\rfloor$

$x_1=\lfloor xq \rfloor$

$x_0=x-\lfloor xq \rfloor$

When $q = 1 / 2$ we get standard binary system.

These operations are reverses of each other and numbers that will give '1', are distributed uniformly among the natural numbers with the probability of '1' equals $q$ ^[1].

x	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
d=0	0	1	2		3	4		5	6		7	8	9		10	11		12	13
d=1				0			1			2				3			4

For example look on the table for $q = 0.3$ ,

$x=18\leftrightarrow(x'=13,d=0)$

$(11,)\leftrightarrow(8,0),\leftrightarrow(6,00),\leftrightarrow(1,001)\leftrightarrow(0,0010)$

[edit] Data compression

A symbol $s$ having probability $q s$ contains $lg(1 / q s)$ bits of information. In $x$ is stored about $lg(x)$ bits.

So as in asymmetric binary system, we should have, that

$x_s\ \ \ is\ approximately\ \ \ x\cdot q_s$

To use asymmetric numeral systems for data compression, we can enforce $x$ to stay in some range, for example $x\in I:=[2^R,2^{R+1}-1]$ . Now if after decoding we get $x < 2 R$ , we can transfer bits from input to the least important bits of $x$ to get it back to $I$ . So before encoding we have to transfer some bits to output, that after encoding we will get back to $I$ .

Practical problem is that decoded and encoded bits are in the reverse order - to use probability prediction methods, we have to make the prediction to the end, than encode in backward order. Now decompression is straightforward. In Matt Mahoney's implementations ^[2] the data is divided into compressed separately segments, for which we store q from the prediction process.

Asymmetric numeral systems works similar as arithmetic coding, but instead of dividing the range into two subranges, we distribute symbols uniformly over the whole range. Intuitively - we place information on the least important position instead of on the most important.

[edit] General case

There are not known practical formulas for larger number of symbols than two, but in fact we only have to define these function on the range ( $I$ ), such that

$x_s\ \ \ is\ approximately\ \ \ x\cdot q_s$

To do this we have to distribute symbols on the range, correspondingly to the probability distribution. We can do it using statistical algorithms.

[edit] See also

Arithmetic coding

[edit] References

^ 3rd section of http://uk.arxiv.org/pdf/0710.3861.pdf
^ fpaqb,fpaqc http://cs.fit.edu/~mmahoney/compression/

[edit] External links

Category:Non-standard positional numeral systems Category:Lossless compression algorithms