Here's a pretty simple way to score the matching. Convert the array of search terms to a regex alternation and count the number of matches for each datum:

my @guesses = ('Place De La Gare', 'Rennes');

my $grei = do {  # this case insensitive re added
    local $" = '|';
    qr/@{[map {quotemeta} @guesses]}/i;
};

my $gre = do {
    local $" = '|';
    qr/@{[map {quotemeta} @guesses]}/;
};

my %score;
for (@data) {
    $score{$_} = () = m/($grei)/g;   # edited.
#   $score{$_} += () = m/($gre)/g;   # uncomment to give extra
                                     # credit for exact match
}
# sort keys by value or grep for threshold to pick best matches
[download]

Update: Case insensitivity was being overruled by the compiled $gre. Repaired. Got rid of non-capture grouping and added quotemeta to defang special characters in the data. More: Added the '()=" trick to force array context - that fixes the counts.

I Like Zaxo

Output after running and using Data::Dumper is

$VAR1 = {
          'Place de la Gare - Bergerac' => 1,
          'Place De La Gare -  Angers' => 0,
          'Place Thiers -  Nancy' => 0,
          'Place De La Gare -  Rennes' => 1,
          'Place de la Gare' => 1,
          'Place De La Gare - Nevers' => 0,
          'Place De La Gare -  Grenoble' => 0,
          'Place De La Gare 1 -  Grenoble' => 0,
          'Place De La Gare - Angers' => 0,
          'Place de la Gare - Libourne' => 1,
          'Place de la Gare - Moutiers' => 1,
          'Place Mohammed V -  Oujda' => 0,
          'Place De La Gare' => 0,
          'Place Du Chateau - Galerie Marchande Du Rer' => 0,
          'Place de la Gare - Quimper' => 1,
          'Place De La Gare -  Nevers' => 0,
          'Place De La Gare - Rennes' => 1
        };
[download]

I would have though that the Rennes match would have a score of 2, it looks to me that its case sensitive (as re-running with the input as 'Place De La Gare' instead of 'Place de la Gare' scores as i would expect. I dont however get why this is seeing as the regex is using -i ?

One approach is to make a reverse index. You might like to check out an article that's an old favorite of mine on Building a Vector Space Search Engine in Perl.

Also Lingua::Stem::Fr may help improve accuracy. Also you can use the above article's suggestion of keeping a bad words list and remove de, la, du, etc. from your dictionary.

But in your guesses you seem to want to do phrase matching, and this is not directly supported. There are more sophisticated algorithms but if you want phrases I'd say the brute force with grepping and keeping track of hits is best for this case, it is not so difficult algorithmically and for only a hundred items it will not be slow if you only loop through once for each word. Note a hash key can have spaces in it.

That said, here is my shot at it. My strategy was simple, and has the added attraction of keeping score, only showing the highest scoring hits, and allowing you to search for phrases. (at least it seems to work that way so far). If you want to use the command line, take a look at @ARGV.

#!/cygdrive/c/Perl/bin/perl

# http://www.perlmonks.org/?node_id=447234

my @loc = ();
my $x;
while (<DATA>) {
    lc; chomp;
    push (@loc,$_);
}

#print "Available locations:\n" . join("\n", sort @loc);

my %score = ();
#my @phrases = ("Place de la Gare", "Rennes");
my @phrases = ("gare","er","n");
my $phrase;

foreach $phrase (@phrases) {
    my @matches = grep(/$phrase/i, @loc);
    foreach my $match (@matches) {
    $score{$match}++;
    }
}

my $hiscore = 0;
foreach my $hit (keys %score) {
    my $s = $score{$hit};
    $hiscore = $s if $s > $hiscore;
    push (@{$hits[$s]},$hit);
}

# just print highest scoring ones

print "Top scoring matches with a score of $hiscore:\n";
foreach my $toploc (@{$hits[$hiscore]}) {
    print "$toploc\n";
}

__DATA__
Place De La Gare - Angers
Place De La Gare - Nevers
Place Mohammed V -  Oujda
Place De La Gare - Rennes
Place de la Gare - Quimper
Place Thiers -  Nancy
Place De La Gare -  Grenoble
Place Du Chateau - Galerie Marchande Du Rer
Place De La Gare -  Angers
Place De La Gare 1 - Bannes Grenoble
Place De La Gare -  Nevers
Place De La Gare -  Rennes
Place De La Gare bannes
Place de la Gare
Place de la Gare - Bergerac
Place de la Gare - Moutiers
Place de la Gare - Libourne
[download]