Return to Answer

Perl - 589 588 583 579 Bytes

Each rule consists of a 1 char head, a body and an underscore. As long as rules can be chopped off the beginnig, the head of the rule is replaced with its body in the rest of the Text. The encoding was done by a Python script using a simple hillclimbing algorithm.

$_="Jell_K w_Hay it
_F other_E9onna _Bmake- _Cve_>ing_<'re_=t's been_: a_;
(Ooh_8o _9 g_6
You_7 t_4 know_5
N%_2nd _3C- up_0 how I'm feel>
_13);)5giC, n%giC
(Gi_- you_&
I justKanna7J-0Gotta Bunderstand
!_%eCrE_#
We'C4n eachF for s8long6r hear=:ch> but6<7o8shy78sHInsideKe both4Kha=9o> on
We47he9ame:2we<EplH_!5gi35let- down5run:rou2a2desert-5Bcry5say9oodbye5tJ: lie:2hurt-
_We< n8strangers78loC647he rules:2s8d8I
A full commitment'sKhat I'm7hink> of6Kouldn't9et7his from:nyF9uy&#A2if-:sk me0Don't7J me-<7o8bli2t8see
!!;,9i3);,9i113)
#&!!";eval"s/$1/$2/g"while s/(.)(.*?)_//s;print

And here the Python code that generates it:

import collections, sys
text = sys.stdin.read().replace('\r\n','\n')
names = set(map(chr,xrange(32,127))) - set('"$()*+./?@[\\]^_|') - set(text)
done = False
while not done:
    done = True
    best = (0, None)
    for m in xrange(1, len(text) / 2 + 1):
        counter = collections.Counter()
        for i in xrange(0, len(text) - m + 1):
            snippet=text[i:i+m]
            if not '_' in snippet:
                counter[snippet] += 1
        for snippet in counter:
            n = counter[snippet]
            gain = n * m - n - (m + 2)
            if gain > best[0]:
                actual_gain = len(text) - len(text.replace(snippet,"")) - n - (m + 2)
                if actual_gain > best[0]:
                    best=(actual_gain, snippet)
                    done=False
    if not done:
        snippet = best[1]
        try:
            name = names.pop()
        except:
            sys.stderr.write('Warning: out of names.\n')
            break
        text = name + snippet + '_' + text.replace(snippet, name)
sys.stdout.write('$_="')
sys.stdout.write(text)
sys.stdout.write('";eval"s/$1/$2/g"while s/(.)(.*?)_//s;print')

Perl - 589 588 583 579 576 Bytes

Each rule consists of a 1 char head, a body and an underscore. As long as rules can be chopped off the beginnig, the head of the rule is replaced with its body in the rest of the Text. The head of the first rule is given, the heads of all following rules are generated from the variable $i.

Since the head for the next rule is placed on the beginning of the text by the previous rule, the last rule will create a character that wont be removed anymore. I had to chose a range of names where the last one would be "W", so i could remove the original "W" from the start of the lyrics, and had it replaced by the rule substitution.

The encoding was done by a Python script using a simple hillclimbing algorithm.

$_="qou_on_er_Hh_ w_
(Ooh_ell_ a_ay it
_'reHoC_g0na _makeR _ve_ oth1 _ing_e ___A_t's been _o _D_4, gP)_
Yq_G_ t_I_ know_
NT_nd _ how I'm feel=
_N_O_i;R up_4)Kgi;, nTgi;
(GP)_ yq_
I just3annaH5RMGotta :und1stand
V_e;r 9_
We';Jn each<for sCl0gFr hearBach= butF8shyHCs7Insid>w>bothJ3haBgo= 0
WeJ2>gam>aLwe'r>9pl7_KgPKletR downKrun6rqLaLdes1tRK:cryKsay goodbyeKt56 li>aLhurtR
_e'r>nCstrang1sHClo;FJ2>rules6LsCdCI
A full commitment's3hat I'm2ink= ofF3qldn't get2is from6ny<guySUALifR6sk meMD0'tH5 meR8bliLtCsee
VVEEQQ
USVV";$i=48;eval"s/$1/$2/g"while s/(.)(.*?)_/chr($i++)/se;print

(I find it remarkable that the compressed Text contains "hearBach" :D)

And here the Python code that generates it:

import collections, sys
text = sys.stdin.read().replace('\r\n','\n')
text = text[1:]
names = list(["q"] + map(chr, xrange(ord('0'), ord('W'))))
done = False
name = ""
while not done:
    done = True
    best = (0, None)
    for m in xrange(1, len(text) / 2 + 1):
        counter = collections.Counter()
        for i in xrange(0, len(text) - m + 1):
            snippet=text[i:i+m]
            if not '_' in snippet:
                counter[snippet] += 1
        for snippet in counter:
            n = counter[snippet]
            gain = n * m - n - (m + 1)
            if gain > best[0]:
                actual_gain = len(text) - len(text.replace(snippet,"")) - n - (m + 1)
                if actual_gain > best[0]:
                    best=(actual_gain, snippet)
                    done=False
    if not done:
        snippet = best[1]
        try:
            lastname = name
            name = names.pop()
            while name in 'ADGION':
                text = name + '_' + text
                name = names.pop()
            while name in '?@':
                text = '_' + text
                name = names.pop()
        except:
            sys.stderr.write('Warning: out of names.\n')
            lastname = "0"
            break
        text = snippet + '_' + text.replace(snippet, name)
sys.stdout.write('$_="')
sys.stdout.write(name + text)
sys.stdout.write('";$i=' + str(ord(lastname)) + ';eval"s/$1/$2/g"while s/(.)(.*?)_/chr($i++)/se;print')

Perl - 589 588 583 Bytes

$_="Qell_L2)
_M w_J;onna _Kay it
_H other_Fmake0 _Eve_B(Ooh_Cing_>'re_<t's been_= a_:o _; g_8
You_9 t_6 know_7
N&_4nd _5 how I'm feelC
_2iE0 up_3B)7giE, n&giE
(GL_0 you_1L3_-
I justManna9Q05Gotta Funderstand!_&eErJ_%
We'E6n eachH for s:long8r hear<=chC but8>9o:shy9:sKInsideMe both6Mha<;oC on
We69he;ame=4we>JplK_#7g27let0 down7run=rou4a4desert07Fcry7say;oodbye7tQ= lie=4hurt0_!
#
_We> n:strangers9:loE869he rules=4s:d:I
A full commitment'sMhat I'm9hinkC of8Mouldn't;et9his from=nyH;uy-%A4if0=sk me5Don't9Q me0>9o:bli4t:see!#

B,;LB,;13%-#!";eval"s/$1/$2/g"while s/(.)(.*?)_//s;print

import collections, sys    
text = sys.stdin.read().replace('\r\n','\n')
names = set(['%c' % c for c in xrange(32,127)]) - set('"$()*+./?@[\\]^_|') - set(text)
done = False
while not done:
    done = True
    best = (0, None)
    for m in xrange(1, len(text) / 2 + 1):
        counter = collections.Counter()
        for i in xrange(0, len(text) - m + 1):
            snippet=text[i:i+m]
            if not '_' in snippet:
                counter[snippet] += 1
        for snippet in counter:
            n = counter[snippet]
            gain = n * m - n - (m + 2)
            if gain > best[0]:
                best=(gain, snippet)
                done=False
    if not done:
        snippet = best[1]
        try:
            name = names.pop()
        except:
            sys.stderr.write('Warning: out of names.\n')
            break
        text = name + snippet + '_' + text.replace(snippet, name)
sys.stdout.write('$_="')
sys.stdout.write(text)
sys.stdout.write('";eval"s/$1/$2/g"while s/(.)(.*?)_//s;print')

Perl - 589 588 583 579 Bytes

$_="Jell_K w_Hay it
_F other_E9onna _Bmake- _Cve_>ing_<'re_=t's been_: a_;
(Ooh_8o _9 g_6
You_7 t_4 know_5
N%_2nd _3C- up_0 how I'm feel>
_13);)5giC, n%giC
(Gi_- you_&
I justKanna7J-0Gotta Bunderstand
!_%eCrE_#
We'C4n eachF for s8long6r hear=:ch> but6<7o8shy78sHInsideKe both4Kha=9o> on
We47he9ame:2we<EplH_!5gi35let- down5run:rou2a2desert-5Bcry5say9oodbye5tJ: lie:2hurt-
_We< n8strangers78loC647he rules:2s8d8I
A full commitment'sKhat I'm7hink> of6Kouldn't9et7his from:nyF9uy&#A2if-:sk me0Don't7J me-<7o8bli2t8see
!!;,9i3);,9i113)
#&!!";eval"s/$1/$2/g"while s/(.)(.*?)_//s;print

import collections, sys
text = sys.stdin.read().replace('\r\n','\n')
names = set(map(chr,xrange(32,127))) - set('"$()*+./?@[\\]^_|') - set(text)
done = False
while not done:
    done = True
    best = (0, None)
    for m in xrange(1, len(text) / 2 + 1):
        counter = collections.Counter()
        for i in xrange(0, len(text) - m + 1):
            snippet=text[i:i+m]
            if not '_' in snippet:
                counter[snippet] += 1
        for snippet in counter:
            n = counter[snippet]
            gain = n * m - n - (m + 2)
            if gain > best[0]:
                actual_gain = len(text) - len(text.replace(snippet,"")) - n - (m + 2)
                if actual_gain > best[0]:
                    best=(actual_gain, snippet)
                    done=False
    if not done:
        snippet = best[1]
        try:
            name = names.pop()
        except:
            sys.stderr.write('Warning: out of names.\n')
            break
        text = name + snippet + '_' + text.replace(snippet, name)
sys.stdout.write('$_="')
sys.stdout.write(text)
sys.stdout.write('";eval"s/$1/$2/g"while s/(.)(.*?)_//s;print')

Perl - 589 588 584 Bytes

for($_="Qell_L2)
_M w_J;onna _Kay it
_H other_Fmake0 _Eve_B(Ooh_Cing_>'re_<t's been_= a_:o _; g_8
You_9 t_6 know_7
N&_4nd _5 how I'm feelC
_2iE0 up_3B)7giE, n&giE
(GL_0 you_1L3_-
I justManna9Q05Gotta Funderstand!_&eErJ_%
We'E6n eachH for s:long8r hear<=chC but8>9o:shy9:sKInsideMe both6Mha<;oC on
We69he;ame=4we>JplK_#7g27let0 down7run=rou4a4desert07Fcry7say;oodbye7tQ= lie=4hurt0_!
#
_We> n:strangers9:loE869he rules=4s:d:I
A full commitment'sMhat I'm9hinkC of8Mouldn't;et9his from=nyH;uy-%A4if0=sk me5Don't9Q me0>9o:bli4t:see!#

B,;LB,;13%-#!";s/(.)(.*?)_//s;){eval"s/$1/$2/g"}print

import collections, sys    
text = sys.stdin.read().replace('\r\n','\n')
names = set(['%c' % c for c in xrange(32,127)]) - set('"$()*+./?@[\\]^_|') - set(text)
done = False
while not done:
    done = True
    best = (0, None)
    for m in xrange(1, len(text) / 2 + 1):
        counter = collections.Counter()
        for i in xrange(0, len(text) - m + 1):
            snippet=text[i:i+m]
            if not '_' in snippet:
                counter[snippet] += 1
        for snippet in counter:
            n = counter[snippet]
            gain = n * m - n - (m + 2)
            if gain > best[0]:
                best=(gain, snippet)
                done=False
    if not done:
        snippet = best[1]
        try:
            name = names.pop()
        except:
            sys.stderr.write('Warning: out of names.\n')
            break
        text = name + snippet + '_' + text.replace(snippet, name)
sys.stdout.write('for($_="')
sys.stdout.write(text)
sys.stdout.write('";s/(.)(.*?)_//s;){eval"s/$1/$2/g"}print')

Perl - 589 588 583 Bytes

$_="Qell_L2)
_M w_J;onna _Kay it
_H other_Fmake0 _Eve_B(Ooh_Cing_>'re_<t's been_= a_:o _; g_8
You_9 t_6 know_7
N&_4nd _5 how I'm feelC
_2iE0 up_3B)7giE, n&giE
(GL_0 you_1L3_-
I justManna9Q05Gotta Funderstand!_&eErJ_%
We'E6n eachH for s:long8r hear<=chC but8>9o:shy9:sKInsideMe both6Mha<;oC on
We69he;ame=4we>JplK_#7g27let0 down7run=rou4a4desert07Fcry7say;oodbye7tQ= lie=4hurt0_!
#
_We> n:strangers9:loE869he rules=4s:d:I
A full commitment'sMhat I'm9hinkC of8Mouldn't;et9his from=nyH;uy-%A4if0=sk me5Don't9Q me0>9o:bli4t:see!#

B,;LB,;13%-#!";eval"s/$1/$2/g"while s/(.)(.*?)_//s;print

import collections, sys    
text = sys.stdin.read().replace('\r\n','\n')
names = set(['%c' % c for c in xrange(32,127)]) - set('"$()*+./?@[\\]^_|') - set(text)
done = False
while not done:
    done = True
    best = (0, None)
    for m in xrange(1, len(text) / 2 + 1):
        counter = collections.Counter()
        for i in xrange(0, len(text) - m + 1):
            snippet=text[i:i+m]
            if not '_' in snippet:
                counter[snippet] += 1
        for snippet in counter:
            n = counter[snippet]
            gain = n * m - n - (m + 2)
            if gain > best[0]:
                best=(gain, snippet)
                done=False
    if not done:
        snippet = best[1]
        try:
            name = names.pop()
        except:
            sys.stderr.write('Warning: out of names.\n')
            break
        text = name + snippet + '_' + text.replace(snippet, name)
sys.stdout.write('$_="')
sys.stdout.write(text)
sys.stdout.write('";eval"s/$1/$2/g"while s/(.)(.*?)_//s;print')