Shape / columns · All operations

Make a column from examples

Derive a column from typed examples of the output.

Status

In arcform

Not built yet

arcform does not do this yet. Its place on the roadmap

Shape of the result
one row out per row in, with columns added or changed
Level
one clause of SQL

What other tools call it

Meridian's classification; an independent blind rating agreed on 86.2% of 312 rows (exact class, version 2).

Trifacta (1)

Background

Making a column from examples fills a new column from a few typed values of the result, by finding a transformation that produces them from the inputs.[1][2] Microsoft Excel's Flash Fill fills the rest of a column once it senses a pattern in the value typed beside the data.[3]

When to use it

Building a column from examples suits an analyst who knows the values the new column should hold but not which transformation, or chain of transformations, gets there.[1] Flash Fill can separate first and last names from a single column, or combine first and last names from two different columns.[3] A study of spreadsheet help forums found that input-output examples were the most common way users described the program they wanted.[4]

Examples are an under-specification of the intended task, so a large number of programs can agree with the same examples.[5] Turning Rick Rashid into Rashid, R. is ambiguous, because the R could come from either the first name or the last.[2] Pick examples that rule out the readings you do not want, such as a person whose first and last names start with different letters. (Meridian's view) Sumit Gulwani's 2011 synthesiser treats the work as interactive, adding examples in each round to make the specification more precise, and it typically converged in 1-4 rounds.[4] Sumit Gulwani's synthesiser can prompt the user for outputs on inputs that may have multiple computational interpretations.[6] Look at the filled rows least like your examples before trusting the column, and add an example for any row it gets wrong. (Meridian's view)

Excel needs the existing data to be consistent enough to recognise a pattern before Flash Fill or Formula by Example can complete a column.[7] A column whose values come in many shapes is a poor fit, because a rule that fits two examples can miss the shapes they did not show. (Meridian's view) Flash Fill generates fixed values that do not update when the source data changes or is added to, so it has to be run again.[7] Keep what the examples produce as an expression rather than as filled values, so that the column is recomputed when the data changes. (Meridian's view)

The method

Sumit Gulwani of Microsoft Research described the method in a 2011 paper, Automating String Processing in Spreadsheets using Input-Output Examples.[6][4] The paper defines a string expression language that supports restricted forms of regular expressions, conditionals and loops, and an algorithm that synthesises a program in it from input-output examples.[6] In Gulwani's language an output is a concatenation of parts, each a constant string, a loop, or a substring of an input marked out by two position expressions.[4] Gulwani designed the language to be expressive enough for the string tasks found in Excel help forums, yet restrictive enough to allow an efficient search for programs.[4]

Flash Fill, developed by Gulwani's team at Microsoft Research with the Office 2013 team, was introduced in Excel 2013.[2] Flash Fill generalises the user's examples into a small program, then runs that program on the remaining rows to fill the output column.[2] Because the number of programs consistent with a small number of examples is so often huge, Flash Fill uses efficient data structures to represent them and machine-learning-based ranking to pick the most likely.[2] Flash Fill uses a version-space algebra (VSA) to represent the large set of programs consistent with the examples succinctly, then ranking to identify the most likely one.[5] A VSA represents an exponential number of programs in polynomial space.[5] Version-space algebra was first introduced by Mitchell in the context of machine learning, and was later used in programming-by-example systems such as SmartEdit and Flash Fill.[5]

Compared with the alternatives

Excel's Formula by Example creates a formula that updates automatically, where Flash Fill fills the column with static text.[7] A rule kept as an expression can be read and checked before it is trusted, which a column of filled values does not allow. (Meridian's view) When you already know the functions a column needs, writing the expression yourself is as quick and leaves nothing to guess. (Meridian's view)

Sources

  1. [1]Add a column from examplesdocumentation
  2. [2]Flash Fill Gives Excel a Smart Chargeorganisation
  3. [3]Using Flash Fill in Exceldocumentation
  4. [4]Automating String Processing in Spreadsheets Using Input-Output Examplessecondary source
  5. [5]BlinkFill: Semi-supervised Programming By Example for Syntactic String Transformationssecondary source
  6. [6]Automating String Processing in Spreadsheets using Input-Output Examples - Microsoft Researchsecondary source
  7. [7]Formula by Example – like Flash Fill but actually usefulsecondary source