Perl自定義按字符串相似度聚類排序

Question

在Perl中，我想以一種自動將類似字符串聚集在一起的方式對不同長度的字符串集合進行排序 。

直覺上，我想我需要一些距離測量每對和 然後聚類例程，按距離分組。

我的字符串數量總是很小而且很短，請參閱下面的示例 。

是否有一個簡單的方法，將做我需要在 sort_magic_here？

#!/usr/bin/perl 
use strict; 

my @list = 
    ("JK_HJ_Lancaster", "SY4_TS_HJ_1000ng", 
    "NB_E_200cc_caHJ_Rep1", "HB_E_100cc_caHJ_Rep1", 
    "HB_E_200cc_caHJ_Rep1", "Normal_Lancaster", 
    "NB15_OP_HJ_1000ng","Zoey_HJ_Slough", 
    "NB_E_100cc_caHJ_Rep1","Normal_Slough", 
    "JK_caHJ_Slough","Zoey_HJ_Lancaster"); 

print "# Straight sort\n"; 
foreach my $elem (sort @list) { 
    print "$elem\n"; 
} 

print "# Sort grouped by string distance\n"; 
foreach my $elem (sort { sort_magic_here() } @list) { 
    print "$elem\n"; 
} 

Answer 1

自定義排序需要兩個輸入，執行「比較」並根據它們是之前，之後還是相等來使用-1,0或1進行響應。

排序是爲了進行排序而設計的，而不是真正用於'分組模糊的類似東西'。

您確實有Text::Levenshtein模塊可以快速計算出來 - 但是您必須做更復雜的事情，因爲在決定排序之前，您需要將每個單詞與每個單詞進行比較。但坦率地說，對於任何「類似詞語」的比較，你都會遇到同樣的問題。

在這裏，你開始看圖論和分組的基礎上。雖然這是一個相當複雜的問題 - 它遠不如'只是'排序那樣微不足道。

我會看喜歡的東西：

#!/usr/bin/perl 
use strict; 
use warnings; 

use Text::Levenshtein qw (distance); 
use Data::Dumper; 

my @list = (
    "JK_HJ_Lancaster",  "SY4_TS_HJ_1000ng", 
    "NB_E_200cc_caHJ_Rep1", "HB_E_100cc_caHJ_Rep1", 
    "HB_E_200cc_caHJ_Rep1", "Normal_Lancaster", 
    "NB15_OP_HJ_1000ng", "Zoey_HJ_Slough", 
    "NB_E_100cc_caHJ_Rep1", "Normal_Slough", 
    "JK_caHJ_Slough",  "Zoey_HJ_Lancaster" 
); 

my %distances; 

foreach my $elem (@list) { 
    foreach my $compare (@list) { 
     next if $elem eq $compare; 
     my $distance = distance($elem, $compare); 
     $distances{$elem}{$compare} = $distance; 
    } 
} 

print Dumper \%distances; 

my %seen; 
my ($cursor) = sort @list; 

while ($cursor) { 
    print "$cursor\n"; 
    $seen{$cursor}++; 
    my @near_words_in_order = 
     sort { $distances{$cursor}{$a} <=> $distances{$cursor}{$b} } 
     keys %{ $distances{$cursor} }; 

    #  print @near_words_in_order; 
    last unless @near_words_in_order; 
    while ($seen{$cursor}) { 
     $cursor = shift(@near_words_in_order) // 0; 
    } 
} 

其中給出結果：

HB_E_100cc_caHJ_Rep1 
HB_E_200cc_caHJ_Rep1 
NB_E_200cc_caHJ_Rep1 
NB_E_100cc_caHJ_Rep1 
NB15_OP_HJ_1000ng 
SY4_TS_HJ_1000ng 
Zoey_HJ_Slough 
JK_caHJ_Slough 
Normal_Slough 
Normal_Lancaster 
JK_HJ_Lancaster 
Zoey_HJ_Lancaster 

至少約團體，如客戶需要以。你可能會更有效率，因爲你不需要計算所有可以減少算法複雜度的距離。但你也會根據接近度和起點得到不同的組。