Vcsn  2.4
Be Rational
levenshtein.hh
Go to the documentation of this file.
1 #pragma once
2 
4 #include <vcsn/dyn/automaton.hh>
5 #include <vcsn/dyn/context.hh>
6 #include <vcsn/misc/vector.hh> // make_vector
7 #include <vcsn/weightset/fwd.hh>
8 
9 namespace vcsn
10 {
12  template <typename Context>
13  mutable_automaton<Context>
14  levenshtein(const Context& ctx)
15  {
16  static_assert(Context::is_lat,
17  "levenshtein: labelset must be a tupleset");
18  static_assert(Context::labelset_t::size() == 2,
19  "levenshtein: labelset must have 2 tapes");
20  static_assert(Context::labelset_t::template valueset_t<0>::has_one(),
21  "levenshtein: first tape must have empty word");
22  static_assert(Context::labelset_t::template valueset_t<1>::has_one(),
23  "levenshtein: second tape must have empty word");
24  static_assert(std::is_same<typename Context::weightset_t, nmin>::value,
25  "levenshtein: weightset must be nmin");
26  using label_t = typename Context::labelset_t::value_t;
27  const auto& ls = *ctx.labelset();
28  const auto& ls1 = ls.template set<0>();
29  const auto& ls2 = ls.template set<1>();
30  const auto& ws = *ctx.weightset();
31  auto letters1 = detail::make_vector(ls1.generators());
32  auto letters2 = detail::make_vector(ls2.generators());
33 
34  auto res = make_mutable_automaton(ctx);
35 
36  auto s = res->new_state();
37  res->set_initial(s);
38  res->set_final(s);
39  // Suppressions.
40  for (auto l : letters1)
41  res->new_transition(s, s, label_t{l, ls2.one()}, 1);
42  // Insertions.
43  for (auto l : letters2)
44  res->new_transition(s, s, label_t{ls1.one(), l}, 1);
45  // Substitutions.
46  for (auto l : letters1)
47  for (auto l2 : letters2)
48  res->new_transition(s, s, label_t{l, l2}, !ls1.equal(l, l2));
49  return res;
50  }
51 
52  /*-------------------.
53  | dyn::levenshtein. |
54  `-------------------*/
55 
56  namespace dyn
57  {
58  namespace detail
59  {
61  template <typename Context>
62  automaton
64  {
65  const auto& c = ctx->as<Context>();
67  }
68  }
69  }
70 }
std::vector< typename Cont::value_type > make_vector(const Cont &cont)
The content of cont as a vector.
Definition: vector.hh:20
return res
Definition: multiply.hh:398
mutable_automaton< Context > levenshtein(const Context &ctx)
The Levenshtein automaton for a given context.
Definition: levenshtein.hh:14
mutable_automaton< Context > make_mutable_automaton(const Context &ctx)
auto & as()
Downcast to the exact type.
Definition: context.hh:36
Definition: a-star.hh:8
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
Template-less root for contexts.
Definition: context.hh:16
automaton levenshtein(const dyn::context &ctx)
Bridge.
Definition: levenshtein.hh:63