Jump to content

Levenshtein distance: Difference between revisions

Levenshtein distance (view source)

Revision as of 06:45, 20 June 2024

890 bytes removed ,  8 days ago
→‎JS ES6: Tidied, updated primitives.
(Add bruijn)
(→‎JS ES6: Tidied, updated primitives.)
Line 2,737:
By composition of generic functions:
<syntaxhighlight lang="javascript">(() => {
'"use strict'";
 
// ------------ LEVENSHTEIN EDIT DISTANCE ------------
 
// levenshtein :: String -> String -> Int
const levenshtein = sa => sb => {
const// csThe =Levenshtein chars(sa);edit distance
const// gobetween =two (ns,given c) => {strings.
const calc = z => tplsb => {
const [c1, x, y]cs = Array[.from(tpl)..sa];
const go = (ns, returnc) minimum([=> {
const calc = z succ(y),=> tpl => {
succconst [c1, x, y] = Array.from(ztpl),;
 
x + (c !== c1 ? 1 : 0)▼
]); return Math.min(
▲ x + (c !== c1 ? 1 :+ 0)y,
go 1 + z,▼
[i]: x + (▼
) : args; c1 === c▼
length: n ? 0▼
: 1
)▼
} );▼
}), { };▼
const [n, ...ns1] = [ns[0], ns.slice(1)];▼
 
return Tuplescanl(vcalc)(a[1].concat(v + n));(▼
enumFromTo zip3(0cs)(cs.lengthns)(ns1)▼
'0': a, );▼
};
 
▲ const [n, ns1] = [ns[0], ns.slice(1)];
return scanl(calc)(succ(n))last(
zip3[...sb].reduce(cs)(ns)(ns1)
ys.slice(1) go,▼
n = args enumFromTo(0)(cs.length;)▼
'1': b, )▼
);
};
return last(▼
chars(sb).reduce(▼
▲ go,
▲ enumFromTo(0)(cs.length)
▲ )
);▼
};▼
 
// ----------------------- TEST ------------------------
const main = () => [
["kitten", "sitting"],
Line 2,773 ⟶ 2,785:
 
 
// ----------------- GENERIC FUNCTIONS -----------------
 
// Tuple (,) :: a -> b -> (a, b)
const Tuple = a =>
b => ({▼
type: 'Tuple',
▲ '0': a,
▲ '1': b,
length: 2
});
 
 
// TupleN :: a -> b ... -> (a, b ... )
function TupleN() {
const
args = Array.from(arguments),
▲ n = args.length;
return 2 < n ? Object.assign(
args.reduce((a, x, i) => Object.assign(a, {
▲ [i]: x
▲ }), {
type: 'Tuple' + n.toString(),
▲ length: n
▲ })
) : args.reduce((f, x) => f(x), Tuple);▼
};
 
 
// chars :: String -> [Char]
const chars = s =>
s.split('');
 
 
// enumFromTo :: Int -> Int -> [Int]
Line 2,814 ⟶ 2,795:
 
// last :: [a] -> a
const last = xs => ({
// The last item of a list.
ysconst n => 0 < ysxs.length ? (;
ys.slice(-1)[0]
) : undefined
)(xs);
 
▲ return last(0 < n
 
// minimum :: Ord a => ? xs[a]n -> a1]
const minimum = xs => ( : null;
▲ };
// The least value of xs.
ys => 0 < ys.length ? (
▲ ys.slice(1)
.reduce((a, y) => y < a ? y : a, ys[0])
) : undefined
)(xs);
 
 
// length :: [a] -> Int
const length = xs =>▼
// Returns Infinity over objects without finite
// length. This enables zip and zipWith to choose
// the shorter argument when one is non-finite,
// like cycle, repeat etc
'GeneratorFunction' !== xs.constructor.constructor.name ? (
xs.length
) : Infinity;
 
 
// scanl :: (b -> a -> b) -> b -> [a] -> [b]
const scanl = f => startValue => xs =>
// The series of interim values arising
xs.reduce((a, x) => {
// from a catamorphism. constParallel vto = f(a[0])(x);foldl.
▲ const length startValue => xs =>
▲ return Tuple(v)(a[1].concat(v));
}, Tuple(startValue) xs.reduce([startValue]))[1];
▲ chars (sba, x).reduce( => {
 
const v = f(a[0])(x);
 
// succ :: Enum a => a -> return [v, a[1].concat(v)];
}, [startValue, [startValue]]
const succ = x =>
1 + x )[1];
 
 
Line 2,860 ⟶ 2,823:
// A function over a pair, derived
// from a curried function.
function (...args) => {
const
args[x, y] = arguments,Boolean(args.length % 2)
xy = Boolean(args.length % 2) ? (args[0]
: args[0];
 
▲ ) : args;
return f(xy[0]x)(xy[1]y);
};
 
Line 2,872 ⟶ 2,835:
// zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
const zip3 = xs =>
ys => zs => xs.slice(
▲ b => ({ 0,
.slice(0, Math.min(...[xs, ys, zs].map(length)))
.map((x, i) => TupleN Math.min(x...[xs, ys[i], zs[i].map(x => x.length));
▲ );
▲ ) : args.reducemap((fx, xi) => f([x), Tupleys[i], zs[i]]);
 
 
// MAIN ---
return JSON.stringify(main());
})();</syntaxhighlight>
{{Out}}
Hout
9,659

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/365583"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information