Search Apps Documentation Source Content File Folder Download Copy Actions Download State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

diff source pure

The diff package implements the Myers diff algorithm to compute the edit distance and generate a minimal edit script ...

Overview

The diff package implements the Myers diff algorithm to compute the edit distance and generate a minimal edit script between two strings.

Edit distance, also known as Levenshtein distance, is a measure of the similarity between two strings. It is defined as the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one string into the other.

Constants 1

const EditKeep, EditInsert, EditDelete 

 1const (
 2	// EditKeep indicates that a character is unchanged in both strings.
 3	EditKeep EditType = iota
 4
 5	// EditInsert indicates that a character was inserted in the new string.
 6	EditInsert
 7
 8	// EditDelete indicates that a character was deleted from the old string.
 9	EditDelete
10)
source

Functions 2

func Format 

1func Format(edits []Edit) string
source

Format converts a slice of Edit operations into a human-readable string representation. It groups consecutive edits of the same type and formats them as follows:

  • Unchanged characters are left as-is
  • Inserted characters are wrapped in [+...]
  • Deleted characters are wrapped in [-...]

This function is useful for visualizing the differences between two strings in a compact and intuitive format.

Parameters:

  • edits: A slice of Edit operations, typically produced by MyersDiff

Returns:

  • A formatted string representing the diff

Example output:

Example
1For the diff between "abcd" and "acbd", the output might be:
2"a[-b]c[+b]d"

Note:

Example
1The function assumes that the input slice of edits is in the correct order.
2An empty input slice will result in an empty string.

func MyersDiff 

1func MyersDiff(old, new string) []Edit
source

MyersDiff computes the difference between two strings using Myers' diff algorithm. It returns a slice of Edit operations that transform the old string into the new string. This implementation finds the shortest edit script (SES) that represents the minimal set of operations to transform one string into the other.

The function handles both ASCII and non-ASCII characters correctly.

Time complexity: O((N+M)D), where N and M are the lengths of the input strings, and D is the size of the minimum edit script.

Space complexity: O((N+M)D)

In the worst case, where the strings are completely different, D can be as large as N+M, leading to a time and space complexity of O((N+M)^2). However, for strings with many common substrings, the performance is much better, often closer to O(N+M).

Parameters:

  • old: the original string.
  • new: the modified string.

Returns:

  • A slice of Edit operations representing the minimum difference between the two strings.

Types 2

type Edit

struct 
1type Edit struct {
2	// Type is the kind of edit operation.
3	Type EditType
4
5	// Char is the character involved in the edit operation.
6	Char rune
7}
source

Edit represent a single edit operation in a diff.

type EditType

ident 
1type EditType uint8
source

EditType represents the type of edit operation in a diff.

Imports 1

  • strings stdlib

Source Files 3