Skip to content

Main content

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.

References

  1. Tool.io on GitHub
  2. Tool.io TypeScript tools library

Similar or alternative tools