And combining merlyn's and my answers I give you:

#!/usr/bin/perl -w

use strict;

use Algorithm::Diff qw( traverse_sequences );

exit main();

{
    my( $outState, %markUp, %htmlEnt );
    BEGIN {
        %markUp= (
            same => ['',''],
            new => ['<strong>','</strong>'],
            old => ['<font size="-1"><strike>','</strike></font>'],
        );
        %htmlEnt= ( "<"=>"lt", "&"=>"amp", ">"=>"gt",
                    "["=>"#91", "]"=>"#93" );
    }
    sub output {
        my( $style, $text )= @_;
        if(  ! defined $outState  ) {
            print $markUp{ $outState= $style }[0];
        } elsif(  $style ne $outState  ) {
            print $markUp{$outState}[1], $markUp{$style}[0];
            $outState= $style;
        }
        $text =~ s#([][<>&])#&$htmlEnt{$1};#g;
        $text =~ s#\n#<br>\n#g;
        print $text;
    }
}

sub flush {
    my( $meth, $rOld, $rNew )= @_;
    return   if  "" eq $$rOld  &&  "" eq $$rNew;
    if(  "" eq $$rOld  ) {
        output( "new", $$rNew );
    } elsif(  "" eq $$rNew  ) {
        output( "old", $$rOld );
    } elsif(  ! $meth  ) {
        output( "old", $$rOld );
        output( "new", $$rNew );
    } else {
        my( $meth, $old, $new )= &$meth( $rOld, $rNew );
        compare( $meth, $old, $new );
    }
    $$rOld= $$rNew= "";
}

sub compare {
    my( $meth, $old, $new )= @_;
    my( $oldTemp, $newTemp )= ( "", "" );
    traverse_sequences( $old, $new, {
        MATCH => sub {      flush( $meth, \$oldTemp, \$newTemp );
                            output( "same", $old->[$_[0]] ) },
        DISCARD_A => sub {  $oldTemp .= $old->[$_[0]] },
        DISCARD_B => sub {  $newTemp .= $new->[$_[1]] },
    } );
    flush( $meth, \$oldTemp, \$newTemp );
}

sub SentToWord {
    my( $rOld, $rNew )= @_;
    return(
        undef,
        [ split /(?<=\s)(?=\S)/, $$rOld ],
        [ split /(?<=\s)(?=\S)/, $$rNew ],
    );
}

sub ParaToSent {
    my( $rOld, $rNew )= @_;
    return(
        \&SentToWord,
        [ split /(?<=[.?!]\s)/, $$rOld ],
        [ split /(?<=[.?!]\s)/, $$rNew ],
    );
}

sub main {
    die "Usage:  $0 old new >dif\n"    unless  2 == @ARGV;
    my( $old, $new );
    { local($/,@ARGV)= ('',$ARGV[0]); $old= [<>]; }
    { local($/,@ARGV)= ('',$ARGV[1]); $new= [<>]; }
    compare( \&ParaToSent, $old, $new );
    output( "same", "" );
    exit 0;
}
[download]

This compares non-HTML files in a way that produces HTML that shows the differences.

Update: I added support for quoting [ and ] and (temporailly) put some sample output from this on my home node.

-- Randal L. Schwartz, Perl hacker

I'd actually convert paragraphs to lines so I could diff those. Then, for each paragraph that was different, convert sentences to lines and diff those. For each of those, convert words to lines and diff those.

Sure, it is difficult, but I think that is the fault of the specification. (:

No one answered half your question so I'll take a stab at it. You need the "bolding" to survive the conversion process to "entities".

The number one suggestion would be to run both texts thru encode_entities BEFORE comparing them. Then your added HTML is safe. A second suggestion would be to use a special chracter that can't appear in the body. like \0175 or some really low char like \f the formfeed char. encode_entities will likely grab that and turn it into something like ý or some so that after encode_entities you can regexp that marker with the html you want. Use one marker for bold on and one for bold off.

--
$you = new YOU;
honk() if $you->love(perl)

FYI, my solution encoded HTML entities by hand during output so the bolding code doesn't get turned into entities.

        - tye (but my friends call me "Tye")