Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Beam search implemented in C++11
// To build this program: g++ -std=c++11 beam_search.cc -o bs
//
#include <iostream>
#include <set>
#include <string>
#include <functional>
#include <map>
#include <utility>
#include <algorithm>
typedef std::string Alphabet;
typedef std::string Sequence; // for operator +, or we can use vector and define +.
typedef std::function<double(const Sequence&, double, char)> ScoreFn;
typedef std::multimap<double, Sequence> Boundary;
void print_boundary(const Boundary& boundary) {
for (auto& t : boundary) {
std::cout << t.first << " : " << t.second << "\n";
}
}
void beam_search(const Alphabet& alphabet, ScoreFn score_fn, int T, size_t K) {
Boundary boundary = { {0.0, ""} };
for (int t = 0; t < T; t++) {
Boundary new_boundary;
for (auto& beam : boundary) {
for (auto& letter : alphabet) {
new_boundary.insert(make_pair(score_fn(beam.second, beam.first, letter),
beam.second + letter));
}
}
size_t k = std::min(K, new_boundary.size());
boundary.clear();
std::copy_n(new_boundary.begin(), k, std::inserter(boundary, boundary.begin()));
print_boundary(boundary);
std::cout << "\n";
}
}
int main() {
const Alphabet alphabet { 'a', 'z' };
beam_search(alphabet,
[](const Sequence& seq, double weight, char letter) {
return weight - static_cast<double>(letter);
},
4, 5);
}
@wangkuiyi

This comment has been minimized.

Copy link
Owner Author

commented Dec 18, 2017

It outputs:

$ g++ -std=c++11 bs.cc -o bs && ./bs
-122 : z
-97 : a

-244 : zz
-219 : za
-219 : az
-194 : aa

-366 : zzz
-341 : zza
-341 : zaz
-341 : azz
-316 : zaa

-488 : zzzz
-463 : zzza
-463 : zzaz
-463 : zazz
-463 : azzz
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.