Bookmark this: tool.io/search/beam-search/source-code
Beam Search Visualizer Source Code
Browse the implementation files for Beam Search Visualizer.tool.ts typescript
// Tool: Beam Search Visualizer
interface SearchNode {
children?: SearchNode[];
label: string;
score: number;
}
const parseInteger = (
input: unknown,
maximum: number
): number | null => {
const value = Number(input);
return Number.isSafeInteger(value) &&
value >= 1 &&
value <= maximum
? value
: null;
};
const parseTree = (input: unknown): SearchNode | null => {
if (typeof input !== 'string' || input.trim() === '')
return null;
try {
const tree: unknown = JSON.parse(input);
let count = 0;
const valid = (
node: unknown,
depth: number
): node is SearchNode => {
count += 1;
const candidate = node as Record<string, unknown>;
if (
count > 10_000 ||
depth > 20 ||
typeof node !== 'object' ||
node === null ||
typeof candidate.label !== 'string' ||
candidate.label.trim() === '' ||
typeof candidate.score !== 'number' ||
!Number.isFinite(candidate.score)
) {
return false;
}
return (
candidate.children === undefined ||
(Array.isArray(candidate.children) &&
candidate.children.length > 0 &&
candidate.children.every((child: unknown) =>
valid(child, depth + 1)
))
);
};
return valid(tree, 0) ? tree : null;
} catch {
return null;
}
};
export const visualizeBeamSearch = (
treeInput: unknown,
beamWidthInput: unknown,
maximumDepthInput: unknown
): string => {
const tree = parseTree(treeInput);
const beamWidth = parseInteger(beamWidthInput, 1_000);
const maximumDepth = parseInteger(maximumDepthInput, 20);
if (
tree === null ||
beamWidth === null ||
maximumDepth === null
) {
return '';
}
type Candidate = {
node: SearchNode;
path: string[];
score: number;
};
let beam: Candidate[] = [
{ node: tree, path: [tree.label], score: tree.score }
];
const levels: Array<{
depth: number;
kept: string[];
pruned: string[];
}> = [];
for (let depth = 1; depth <= maximumDepth; depth += 1) {
const expanded = beam.flatMap((candidate) =>
(candidate.node.children ?? []).map((node) => ({
node,
path: [...candidate.path, node.label],
score: candidate.score + node.score
}))
);
if (expanded.length === 0) break;
expanded.sort(
(first, second) =>
second.score - first.score ||
first.path
.join('>')
.localeCompare(second.path.join('>'))
);
beam = expanded.slice(0, beamWidth);
levels.push({
depth,
kept: beam.map(({ path }) => path.join(' > ')),
pruned: expanded
.slice(beamWidth)
.map(({ path }) => path.join(' > '))
});
}
const best = beam[0];
return JSON.stringify(
{
bestPath: best.path,
bestScore: best.score,
levels,
terminal: best.node.children === undefined
},
null,
2
);
};
const DEFAULT_TREE =
'{"label":"root","score":0,"children":[{"label":"A","score":3,"children":[{"label":"A1","score":2},{"label":"A2","score":5}]},{"label":"B","score":2,"children":[{"label":"B1","score":8},{"label":"B2","score":1}]}]}';
export const Tool: TypeTool = {
name: 'Beam Search Visualizer',
slug: 'search/beam-search',
intro:
'Expand a scored tree breadth-first while retaining only the highest-scoring paths at each depth.',
tool: visualizeBeamSearch,
i: [
{
example: DEFAULT_TREE,
label: 'Search Tree',
placeholder: 'JSON scored tree',
render: 'textarea',
type: 'text',
value: DEFAULT_TREE
},
{
example: '2',
label: 'Beam Width',
placeholder: 'Paths retained per level',
type: 'number',
value: 2
},
{
example: '10',
label: 'Maximum Depth',
placeholder: 'Maximum levels to expand',
type: 'number',
value: 10
}
],
o: [
{
example: '{ "bestPath": [], "levels": [] }',
label: 'Beam Search',
placeholder: 'Beam trace will appear here...',
render: 'textarea',
type: 'text'
}
],
cite: [
{
title: 'Best-First Beam Search',
url: 'https://arxiv.org/abs/2007.03909'
},
{
title: 'Beam search — Wikipedia',
url: 'https://en.wikipedia.org/wiki/Beam_search'
}
]
};
export default Tool;
Description
Browse the implementation files for Beam Search Visualizer.