[text-levenshtein-edlib.git] / lib / Text / Levenshtein / Edlib.pm

package Text::Levenshtein::Edlib;

use 5.014000;
use strict;
use warnings;
use Carp;
use parent qw/Exporter/;

my @constants =
  qw/
		EDLIB_CIGAR_EXTENDED
		EDLIB_CIGAR_STANDARD
		EDLIB_EDOP_DELETE
		EDLIB_EDOP_INSERT
		EDLIB_EDOP_MATCH
		EDLIB_EDOP_MISMATCH
		EDLIB_MODE_HW
		EDLIB_MODE_NW
		EDLIB_MODE_SHW
		EDLIB_STATUS_ERROR
		EDLIB_STATUS_OK
		EDLIB_TASK_DISTANCE
		EDLIB_TASK_LOC
		EDLIB_TASK_PATH/;

our %EXPORT_TAGS =
  (all => [ @constants, qw/align distance to_cigar/ ], constants => \@constants);
our @EXPORT_OK = ( @{ $EXPORT_TAGS{'all'} } );
our @EXPORT = ( @{ $EXPORT_TAGS{'constants'} } );
our $VERSION = '0.001001';

require XSLoader;
XSLoader::load('Text::Levenshtein::Edlib', $VERSION);

sub AUTOLOAD {
	# This AUTOLOAD is used to 'autoload' constants from the constant()
	# XS function.

	my $constname;
	our $AUTOLOAD;
	($constname = $AUTOLOAD) =~ s/.*:://;
	croak "&Text::Levenshtein::Edlib::constant not defined" if $constname eq 'constant';
	my ($error, $val) = constant($constname);
	if ($error) { croak $error; }
	{
		no strict 'refs';
		*$AUTOLOAD = sub { $val };
	}
	goto &$AUTOLOAD;
}

sub align {
	my ($q, $t, $k, $mode, $task) = @_;
	$k //= -1;
	$mode //= EDLIB_MODE_NW();
	$task //= EDLIB_TASK_PATH();
	my $result = edlibAlign($q, $t, $k, $mode, $task);
	my ($dist, $alpha_len, $end, $start, $align) = @$result;
	return {} if $dist == -1;
	my %ret;
	$ret{editDistance}   = $dist;
	$ret{alphabetLength} = $alpha_len;
	$ret{endLocations}   = $end   if defined $end;
	$ret{startLocations} = $start if defined $start;
	$ret{alignment}      = $align if defined $align;
	\%ret
}

sub distance {
	my ($q, $t, $k, $mode) = @_;
	align($q, $t, $k, $mode, EDLIB_TASK_DISTANCE())->{editDistance}
}

sub to_cigar {
	my ($align, $format) = @_;
	$align = pack 'C*', @$align;
	$format //= EDLIB_CIGAR_STANDARD();
	edlibAlignmentToCigar($align, $format);
}

1;
__END__

=encoding utf-8

=head1 NAME

Text::Levenshtein::Edlib - XS edit distance and optimal alignment path calculation

=head1 SYNOPSIS

  use feature 'say';

  use Text::Levenshtein::Edlib qw/:all/;
  say distance 'kitten', 'sitting'; # prints '3'
  say 'Distance > 2!'
      if !defined distance 'kitten', 'sitting', 2; # prints 'Distance > 2!'

  my $align = align('kitten', 'sitting');
  say "Edit distance is: $align->{editDistance}";
  say "Alphabet length is: $align->{alphabetLength}";
  say "Start locations are: @{$align->{startLocations}}";
  say "End locations are: @{$align->{endLocations}}";
  say "Alignment path is: @{$align->{alignment}}";
  say "Alignment path (in CIGAR format): ", to_cigar $align->{alignment};
  say "Alignment path (in extended CIGAR format): ",
      to_cigar $align->{alignment}, EDLIB_CIGAR_EXTENDED;

=head1 DESCRIPTION

Text::Levenshtein::Edlib is a wrapper around the edlib library that
computes Levenshtein edit distance and optimal alignment path for a
pair of strings.

It B<does not handle UTF-8 strings>, for those
L<Text::Levenshtein::XS> can compute edit distance but not alignment
path.

This module has two functions:

=over

=item B<distance>(I<$query>, I<$target>, [I<$max_distance>, [I<$mode>]])

This is the basic interface to the library. It is compatible with the
function of the same name in L<Text::Levenshtein::XS>.

It returns the edit distance between the two given strings. If the
third argument is specified, and the edit distance is greater than the
value of the third argument, then the function finishes the
computation early and returns undef. See below for the meaning of the
optional I<$mode> argument.

=item B<align>(I<$query>, I<$target>, [I<$max_distance>, [I<$mode>, [I<$task>]]])

This is the full-featured interface to the library.

It returns a hashref with the following keys:

=over

=item C<editDistance>

The edit distance of the two strings.

=item C<alphabetLength>

The number of different characters in the query and target together.

=item C<endLocations>

Array of zero-based positions in target where optimal alignment paths
end. If gap after query is penalized, gap counts as part of query
(NW), otherwise not.

=item C<startLocations>

Array of zero-based positions in target where optimal alignment paths
start, they correspond to endLocations. If gap before query is
penalized, gap counts as part of query (NW), otherwise not.

=item C<alignment>

Alignment is found for first pair of start and end locations.
Alignment is sequence of numbers: 0, 1, 2, 3. 0 stands for match. 1
stands for insertion to target. 2 stands for insertion to query. 3
stands for mismatch. You can use the C<EDLIB_EDOP_*> constants instead
of 0, 1, 2, and 3. Alignment aligns query to target from begining of
query till end of query. If gaps are not penalized, they are not in
alignment.

=back

The third argument, I<$max_distance>, works similarly to the third
argument of B<distance>: if the distance is more than its value, this
function returns an empty hashref. Default value is -1, which disables
this optimization.

The fourth argument, I<$mode>, chooses how Edlib should treat gaps
before and after query. The options are:

=over

=item C<EDLIB_MODE_NW> (default)

Global method - gaps are not ignored. This is the standard Levenshtein
distance, and is the default if I<$mode> is not specified.

=item C<EDLIB_MODE_SHW>

Prefix method - gaps at query end are ignored. So the edit distance
between C<AACT> and C<AACTGGC> is 0, because we can ignore the C<GGC>
at the end.

=item C<EDLIB_MODE_HW>

Infix method - gaps at both query start and end are ignored. So the
edit distance between C<ACT> and C<CGACTGAC> is 0, because C<CG> at
the beginning and C<GAC> at the end of the target are ignored.

=back

The fifth argument, I<$task>, chooses what we want to compute. The options are:

=over

=item C<EDLIB_TASK_PATH> (default, slowest)

All the keys described above will be computed.

=item C<EDLIB_TASK_LOC>

All keys except for C<alignment> will be computed.

=item C<EDLIB_TASK_DISTANCE> (fastest)

All keys except for C<alignment> and C<startLocations> will be computed.

=back

The less the function computes, the faster it runs.

=back

=head2 EXPORT

All constants by default. You can export the functions C<align>,
C<distance> and C<to_cigar> and any of the constants below. You can
use the tags C<:constants> to export every constant, and C<:all> to
export every constant, C<align>, C<distance> and C<to_cigar>.

=head2 Exportable constants

  EDLIB_CIGAR_EXTENDED
  EDLIB_CIGAR_STANDARD
  EDLIB_EDOP_DELETE
  EDLIB_EDOP_INSERT
  EDLIB_EDOP_MATCH
  EDLIB_EDOP_MISMATCH
  EDLIB_MODE_HW
  EDLIB_MODE_NW
  EDLIB_MODE_SHW
  EDLIB_STATUS_ERROR
  EDLIB_STATUS_OK
  EDLIB_TASK_DISTANCE
  EDLIB_TASK_LOC
  EDLIB_TASK_PATH

=head1 SEE ALSO

L<https://github.com/Martinsos/edlib/>, L<http://martinsosic.com/edlib/edlib_8h.html>

=head1 AUTHOR

Marius Gavrilescu, E<lt>marius@ieval.roE<gt>

=head1 COPYRIGHT AND LICENSE

Copyright (C) 2017 by Marius Gavrilescu

This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself, either Perl version 5.22.3 or,
at your option, any later version of Perl 5 you may have available.


=cut
Commit	Line	Data
a99d15a3 MG	1	package Text::Levenshtein::Edlib;
	2
	3	use 5.014000;
	4	use strict;
	5	use warnings;
	6	use Carp;
	7	use parent qw/Exporter/;
	8
	9	my @constants =
	10	qw/
	11	EDLIB_CIGAR_EXTENDED
	12	EDLIB_CIGAR_STANDARD
	13	EDLIB_EDOP_DELETE
	14	EDLIB_EDOP_INSERT
	15	EDLIB_EDOP_MATCH
	16	EDLIB_EDOP_MISMATCH
	17	EDLIB_MODE_HW
	18	EDLIB_MODE_NW
	19	EDLIB_MODE_SHW
	20	EDLIB_STATUS_ERROR
	21	EDLIB_STATUS_OK
	22	EDLIB_TASK_DISTANCE
	23	EDLIB_TASK_LOC
	24	EDLIB_TASK_PATH/;
	25
	26	our %EXPORT_TAGS =
329961ff	27	(all => [ @constants, qw/align distance to_cigar/ ], constants => \@constants);
a99d15a3 MG	28	our @EXPORT_OK = ( @{ $EXPORT_TAGS{'all'} } );
a99d15a3 MG	29	our @EXPORT = ( @{ $EXPORT_TAGS{'constants'} } );
c4b849c0	30	our $VERSION = '0.001001';
a99d15a3 MG	31
	32	require XSLoader;
	33	XSLoader::load('Text::Levenshtein::Edlib', $VERSION);
	34
	35	sub AUTOLOAD {
	36	# This AUTOLOAD is used to 'autoload' constants from the constant()
	37	# XS function.
	38
	39	my $constname;
	40	our $AUTOLOAD;
	41	($constname = $AUTOLOAD) =~ s/.*:://;
	42	croak "&Text::Levenshtein::Edlib::constant not defined" if $constname eq 'constant';
	43	my ($error, $val) = constant($constname);
	44	if ($error) { croak $error; }
	45	{
	46	no strict 'refs';
	47	*$AUTOLOAD = sub { $val };
	48	}
	49	goto &$AUTOLOAD;
	50	}
	51
	52	sub align {
	53	my ($q, $t, $k, $mode, $task) = @_;
	54	$k //= -1;
	55	$mode //= EDLIB_MODE_NW();
	56	$task //= EDLIB_TASK_PATH();
	57	my $result = edlibAlign($q, $t, $k, $mode, $task);
	58	my ($dist, $alpha_len, $end, $start, $align) = @$result;
	59	return {} if $dist == -1;
	60	my %ret;
	61	$ret{editDistance} = $dist;
	62	$ret{alphabetLength} = $alpha_len;
	63	$ret{endLocations} = $end if defined $end;
	64	$ret{startLocations} = $start if defined $start;
	65	$ret{alignment} = $align if defined $align;
	66	\%ret
	67	}
	68
	69	sub distance {
159e7b25 MG	70	my ($q, $t, $k, $mode) = @_;
159e7b25 MG	71	align($q, $t, $k, $mode, EDLIB_TASK_DISTANCE())->{editDistance}
a99d15a3 MG	72	}
a99d15a3 MG	73
329961ff MG	74	sub to_cigar {
	75	my ($align, $format) = @_;
	76	$align = pack 'C*', @$align;
	77	$format //= EDLIB_CIGAR_STANDARD();
	78	edlibAlignmentToCigar($align, $format);
	79	}
	80
a99d15a3 MG	81	1;
	82	__END__
	83
	84	=encoding utf-8
	85
	86	=head1 NAME
	87
	88	Text::Levenshtein::Edlib - XS edit distance and optimal alignment path calculation
	89
	90	=head1 SYNOPSIS
	91
	92	use feature 'say';
	93
	94	use Text::Levenshtein::Edlib qw/:all/;
	95	say distance 'kitten', 'sitting'; # prints '3'
	96	say 'Distance > 2!'
	97	if !defined distance 'kitten', 'sitting', 2; # prints 'Distance > 2!'
	98
	99	my $align = align('kitten', 'sitting');
	100	say "Edit distance is: $align->{editDistance}";
	101	say "Alphabet length is: $align->{alphabetLength}";
	102	say "Start locations are: @{$align->{startLocations}}";
	103	say "End locations are: @{$align->{endLocations}}";
	104	say "Alignment path is: @{$align->{alignment}}";
329961ff MG	105	say "Alignment path (in CIGAR format): ", to_cigar $align->{alignment};
	106	say "Alignment path (in extended CIGAR format): ",
	107	to_cigar $align->{alignment}, EDLIB_CIGAR_EXTENDED;
a99d15a3 MG	108
	109	=head1 DESCRIPTION
	110
	111	Text::Levenshtein::Edlib is a wrapper around the edlib library that
	112	computes Levenshtein edit distance and optimal alignment path for a
	113	pair of strings.
	114
	115	It B<does not handle UTF-8 strings>, for those
	116	L<Text::Levenshtein::XS> can compute edit distance but not alignment
	117	path.
	118
	119	This module has two functions:
	120
	121	=over
	122
159e7b25	123	=item B<distance>(I<$query>, I<$target>, [I<$max_distance>, [I<$mode>]])
a99d15a3 MG	124
	125	This is the basic interface to the library. It is compatible with the
	126	function of the same name in L<Text::Levenshtein::XS>.
	127
	128	It returns the edit distance between the two given strings. If the
	129	third argument is specified, and the edit distance is greater than the
	130	value of the third argument, then the function finishes the
159e7b25 MG	131	computation early and returns undef. See below for the meaning of the
159e7b25 MG	132	optional I<$mode> argument.
a99d15a3 MG	133
	134	=item B<align>(I<$query>, I<$target>, [I<$max_distance>, [I<$mode>, [I<$task>]]])
	135
	136	This is the full-featured interface to the library.
	137
	138	It returns a hashref with the following keys:
	139
	140	=over
	141
	142	=item C<editDistance>
	143
	144	The edit distance of the two strings.
	145
	146	=item C<alphabetLength>
	147
	148	The number of different characters in the query and target together.
	149
	150	=item C<endLocations>
	151
	152	Array of zero-based positions in target where optimal alignment paths
	153	end. If gap after query is penalized, gap counts as part of query
	154	(NW), otherwise not.
	155
	156	=item C<startLocations>
	157
	158	Array of zero-based positions in target where optimal alignment paths
	159	start, they correspond to endLocations. If gap before query is
	160	penalized, gap counts as part of query (NW), otherwise not.
	161
	162	=item C<alignment>
	163
	164	Alignment is found for first pair of start and end locations.
	165	Alignment is sequence of numbers: 0, 1, 2, 3. 0 stands for match. 1
	166	stands for insertion to target. 2 stands for insertion to query. 3
	167	stands for mismatch. You can use the C<EDLIB_EDOP_*> constants instead
	168	of 0, 1, 2, and 3. Alignment aligns query to target from begining of
	169	query till end of query. If gaps are not penalized, they are not in
	170	alignment.
	171
	172	=back
	173
	174	The third argument, I<$max_distance>, works similarly to the third
	175	argument of B<distance>: if the distance is more than its value, this
	176	function returns an empty hashref. Default value is -1, which disables
	177	this optimization.
	178
	179	The fourth argument, I<$mode>, chooses how Edlib should treat gaps
	180	before and after query. The options are:
	181
	182	=over
	183
	184	=item C<EDLIB_MODE_NW> (default)
	185
	186	Global method - gaps are not ignored. This is the standard Levenshtein
	187	distance, and is the default if I<$mode> is not specified.
	188
	189	=item C<EDLIB_MODE_SHW>
	190
	191	Prefix method - gaps at query end are ignored. So the edit distance
	192	between C<AACT> and C<AACTGGC> is 0, because we can ignore the C<GGC>
	193	at the end.
	194
	195	=item C<EDLIB_MODE_HW>
	196
197	Infix method - gaps at both query start and end are ignored. So the
198	edit distance between C<ACT> and C<CGACTGAC> is 0, because C<CG> at
199	the beginning and C<GAC> at the end of the target are ignored.
200
201	=back
202
a35dd4c3 MG	203	The fifth argument, I<$task>, chooses what we want to compute. The options are:
	204
	205	=over
	206
	207	=item C<EDLIB_TASK_PATH> (default, slowest)
	208
	209	All the keys described above will be computed.
	210
	211	=item C<EDLIB_TASK_LOC>
	212
	213	All keys except for C<alignment> will be computed.
	214
	215	=item C<EDLIB_TASK_DISTANCE> (fastest)
	216
	217	All keys except for C<alignment> and C<startLocations> will be computed.
	218
	219	=back
	220
	221	The less the function computes, the faster it runs.
a99d15a3 MG	222
	223	=back
	224
	225	=head2 EXPORT
	226
a35dd4c3 MG	227	All constants by default. You can export the functions C<align>,
	228	C<distance> and C<to_cigar> and any of the constants below. You can
	229	use the tags C<:constants> to export every constant, and C<:all> to
	230	export every constant, C<align>, C<distance> and C<to_cigar>.
a99d15a3 MG	231
	232	=head2 Exportable constants
	233
	234	EDLIB_CIGAR_EXTENDED
	235	EDLIB_CIGAR_STANDARD
	236	EDLIB_EDOP_DELETE
	237	EDLIB_EDOP_INSERT
	238	EDLIB_EDOP_MATCH
	239	EDLIB_EDOP_MISMATCH
	240	EDLIB_MODE_HW
	241	EDLIB_MODE_NW
	242	EDLIB_MODE_SHW
	243	EDLIB_STATUS_ERROR
	244	EDLIB_STATUS_OK
	245	EDLIB_TASK_DISTANCE
	246	EDLIB_TASK_LOC
	247	EDLIB_TASK_PATH
	248
	249	=head1 SEE ALSO
	250
ed67b619	251	L<https://github.com/Martinsos/edlib/>, L<http://martinsosic.com/edlib/edlib_8h.html>
a99d15a3 MG	252
	253	=head1 AUTHOR
	254
	255	Marius Gavrilescu, E<lt>marius@ieval.roE<gt>
	256
	257	=head1 COPYRIGHT AND LICENSE
	258
	259	Copyright (C) 2017 by Marius Gavrilescu
	260
	261	This library is free software; you can redistribute it and/or modify
	262	it under the same terms as Perl itself, either Perl version 5.22.3 or,
	263	at your option, any later version of Perl 5 you may have available.
	264
	265
	266	=cut