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

自定义排序接受两个输入，执行 'comparison' 并根据它们是在之前、之后还是相等以 -1、0 或 1 响应。

排序是为了确定位置顺序而设计的，而不是真正用于“将模糊相似的东西分组”。

您确实有 Text::Levenshtein 模块可以让您快速计算 - 但您必须做一些完全更复杂的事情，因为您需要将每个词与其他词进行比较才能决定排序.但坦率地说，任何 'similar words' 类比较都会遇到同样的问题。

在此，您将开始研究图论和基于此的分组。这是一个相当复杂的问题 - 它远非 'just' 排序那么简单。

我会看一些东西，比如：

#!/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

这至少大致符合您的要求。您可能会更高效，因为您不需要计算所有距离，这会降低算法的复杂性。但是你也会根据距离和起点得到不同的组。

perl 自定义按字符串相似度聚类排序

perl custom sort by string similarity clustering

sorting

perl

levenshtein-distance