We're no strangers to code golf, you know the rules, and so do I Write the shortest program that prints the entire lyrics of "Never Gonna Give You Up" by Rick Astley.

Rules:


Must output the lyrics exactly as they appear in the above pastebin*. Here's the raw dump: http://pastebin.com/raw/wwvdjvEj
Cannot rely on any external resources - all lyrics must be generated by / embedded in code.
No use of existing compression algorithms (e.g. gzip / bzip2) unless you include the full algorithm in your code.
Use any language, shortest code wins.


Update, 1st June 2012:
For solutions containing non-ASCII text, the size of your solution will be counted in bytes, based on UTF-8 encoding. If you use codepoints that cannot be encoded in UTF-8, your solution will not be judged as valid.

Update, 7th June 2012:
Thank you all for your awesome solutions! I'll be accepting the shortest answer tomorrow afternoon. Right now, Peter Taylor's GolfScript answer is winning, so get cracking on some improvements if you want to beat him! :)

*There is a typo in the Pastebin (line 46, "know" should be "known").  You may either replicate it or not at your discretion.
Ruby 576 557 556 (552) chars &amp;&amp; PHP 543 chars

Another search-and-replace solution. Note that this form of solution is essentially a Grammar-based Compression Code http://en.wikipedia.org/wiki/Grammar-based_code
Check out http://www.cs.washington.edu/education/courses/csep590a/07au/lectures/lecture05small.pdf for a simple to understand compression example. 

I've written the substitution rules so that the starting character for each substitution is computed (they are in sequential ASCII order); it need not be present in the transition data.

i=44
s="We; n7trangMsL8loT63Ke rules5s8d8I
AJull commit4nt'sChatFKink: of6CHldn'tRetKisJrom&lt;ny@Ruy-/A= if?&lt;sk 42DS'tLE 4?;Lo8bli=L7ee..
O,R1)O,R001)/-.."
"
I justCannaLE?2Gotta &gt;u=Msta=.|
Ng1Nlet? downNrun&lt;rH=5desMt?N&gt;cryNsayRoodbyeNtE&lt; lie5hurt?|

We'T3n each@Jor s8lSg6r hear9&lt;ch: but6;Lo7hyL7BInsideCe both3Cha9Ro: S
We3KeRa45we;QplB|1)O)NgiT, nPgiT
(G|iT? up| howFJeel:
| know|me|&lt;= |
YH|8s|o |t's been|ing|'re| a|nd|make? | yH| othM|A|ay it
| w|D|ell| I'm|G|ou|I| f|Lh| t|er|
NP|
(Ooh|eTrQ|RSna | g|on|ve".scan(/[^|]+/){s.gsub!((i+=1).chr,$&amp;)}
puts s


implementation notes


The above solution is 556 chars long, but scores 552 with the removal of newlines from source code. It is slightly better scoring than the original 556 char solution I had that scored 554. 
I use "known" instead of "know"; this makes the verse repetition identical and should make the compression better
I originally optimized the rules by repeatedly searching for the substitution that would yield the most decrease in current code size. However, I found that RiderOfGiraffe's substitution rules were (slightly) better than mine, so I'm now using a modified version of his rules.
I spent time reordering the rules so that a single substitution pass can decompress everything.
Due to the computed initial character in the substitution rules, my rule list has a rule for every character in a contiguous ASCII range. I found that having some "dummy" substitution rules was better for code size than having all real rules and coding a final text fixup substitution. 
This example is small enough that you probably could successfully write a program to find the optimal (least total cost) set of rules. I would not expect doing this would yield size reductions of more than a few bytes.


older implementation

This older implementation has 576 characters and started with substitution rules from ugoren's bash/sed implementation. Ignoring the substitution variable renaming, my first 28 substitutions are exactly the same as those performed in ugoren's program. I added a few more to lower the overall byte count. This is possible because my rules are more efficiently represented than those in ugoren's implementation. 

i=44
puts"WeM noHtraLersB loJ;6 C rules=so do $
&amp; full commitment'sGhat&lt;thinkDof;Gouldn'tKet this fromFny oCrKuy.
-&amp;E if9ask me1~on't @ me:MBo bliEBHee//

3300-.//|
We'J6n each oCr forHo loL;r hear2FchDbut;MBoHhyBH7$nsideGe both6Gha2ADon
We6 CKame=weM&gt;pl7|
$ justGanna @:1#otta 8uEerstaE/|
5?9up5let9down5runFrouE=desert:58cry5sayAodbye5@F lie=hurt:|(Ooh)5?, nI&gt;?
(#4| how&lt;feeliL
|t's been|(Ooh,K4|iJ9up)
|
NI&gt;| know|ay it
|make9|: | you|
You| $'m |FE |Anna |giJ|tell|Ko| to|the|iL |nd| a| w| s|eJr|ve| g|ng|'re".split("|").inject{|m,o|m.gsub((i+=1).chr,o)}.tr('&amp;~#$',"ADGI")


I did not try optimizing the substitution rules in this one.

contest notes

The search-and-replace decompression scheme works well for this contest because most languages have pre-built routines that can do this. With such a small amount of text to be generated, complex decompression schemes do not seem to be feasible winners.

I've used only ASCII text and also avoided using unprintable ASCII characters. With these restrictions, each character in your code can only represent up to a maximum of 6.6 bits of information; this is very different than to real compression techniques where you use all 8 bits. In some sense, it is not "fair" to compare to gzip/bzip2 code size because those algorithms will use all 8 bits. A fancier decompression algorithm may be possible if you can include traditionally unprintable ASCII in your strings AND each unprintable character is still written in your code as a single byte.

PHP Solution

&lt;?=str_replace(range('-',T),split(q,"
I justCannaLE?2Gotta &gt;u=Msta=.q
Ng1Nlet? downNrun&lt;rH=5desMt?N&gt;cryNsayRoodbyeNtE&lt; lie5hurt?q

We'T3n each@Jor s8lSg6r hear9&lt;ch: but6;Lo7hyL7BInsideCe both3Cha9Ro: S
We3KeRa45we;QplBq1)O)NgiT, nPgiT
(GqiT? upq howFJeel:
q knowqmeq&lt;= q
YHq8sqo qt's beenqingq'req aqndqmake? q yHq othMqAqay it
q wqDqellq I'mqGqouqIq fqLhq tqerq
NPq
(OohqeTrQqRSna q gqonqve"),"We; n7trangMsL8loT63Ke rules5s8d8I
AJull commit4nt'sChatFKink: of6CHldn'tRetKisJrom&lt;ny@Ruy-/A= if?&lt;sk 42DS'tLE 4?;Lo8bli=L7ee..
O,R1)O,R001)/-..");


The above solution takes the PHP from "a sad dude" and combines it with my substitution rules. The PHP answer turns out to have the shortest decompression code. See http://ideone.com/XoW5t