public function interleave_changed_lines( $orig, $final ) {

		// Contains all pairwise string comparisons. Keys are such that this need only be a one dimensional array.
		$matches = array();
		foreach ( array_keys( $orig ) as $o ) {
			foreach ( array_keys( $final ) as $f ) {
				$matches[ "$o,$f" ] = $this->compute_string_distance( $orig[ $o ], $final[ $f ] );
			}
		}
		asort( $matches ); // Order by string distance.

		$orig_matches  = array();
		$final_matches = array();

		foreach ( $matches as $keys => $difference ) {
			list($o, $f) = explode( ',', $keys );
			$o           = (int) $o;
			$f           = (int) $f;

			// Already have better matches for these guys
			if ( isset( $orig_matches[ $o ] ) && isset( $final_matches[ $f ] ) ) {
				continue;
			}

			// First match for these guys. Must be best match
			if ( ! isset( $orig_matches[ $o ] ) && ! isset( $final_matches[ $f ] ) ) {
				$orig_matches[ $o ]  = $f;
				$final_matches[ $f ] = $o;
				continue;
			}

			// Best match of this final is already taken?  Must mean this final is a new row.
			if ( isset( $orig_matches[ $o ] ) ) {
				$final_matches[ $f ] = 'x';
			} elseif ( isset( $final_matches[ $f ] ) ) {
				// Best match of this orig is already taken?  Must mean this orig is a deleted row.
				$orig_matches[ $o ] = 'x';
			}
		}

		// We read the text in this order
		ksort( $orig_matches );
		ksort( $final_matches );

		// Stores rows and blanks for each column.
		$orig_rows      = array_keys( $orig_matches );
		$orig_rows_copy = $orig_rows;
		$final_rows     = array_keys( $final_matches );

		// Interleaves rows with blanks to keep matches aligned.
		// We may end up with some extraneous blank rows, but we'll just ignore them later.
		foreach ( $orig_rows_copy as $orig_row ) {
			$final_pos = array_search( $orig_matches[ $orig_row ], $final_rows, true );
			$orig_pos  = (int) array_search( $orig_row, $orig_rows, true );

			if ( false === $final_pos ) { // This orig is paired with a blank final.
				array_splice( $final_rows, $orig_pos, 0, -1 );
			} elseif ( $final_pos < $orig_pos ) { // This orig's match is up a ways. Pad final with blank rows.
				$diff_array = range( -1, $final_pos - $orig_pos );
				array_splice( $final_rows, $orig_pos, 0, $diff_array );
			} elseif ( $final_pos > $orig_pos ) { // This orig's match is down a ways. Pad orig with blank rows.
				$diff_array = range( -1, $orig_pos - $final_pos );
				array_splice( $orig_rows, $orig_pos, 0, $diff_array );
			}
		}

		// Pad the ends with blank rows if the columns aren't the same length
		$diff_count = count( $orig_rows ) - count( $final_rows );
		if ( $diff_count < 0 ) {
			while ( $diff_count < 0 ) {
				array_push( $orig_rows, $diff_count++ );
			}
		} elseif ( $diff_count > 0 ) {
			$diff_count = -1 * $diff_count;
			while ( $diff_count < 0 ) {
				array_push( $final_rows, $diff_count++ );
			}
		}

		return array( $orig_matches, $final_matches, $orig_rows, $final_rows );
	}