[nerv_]

Какие тут могут быть идеи, это банальная задача на вычисление редакционного расстояния Левенштейна.
Если нужна транспозиция, то Дамерау — Левенштейна.

Мне почему то кажется, что ты не так понял. Задача не найти "похожие с учетом k различий", а "поиск по точному совпадению" (если можно так выразится).

Грубо говоря у него есть два массива, ему надо пробежаться циклом по одному и проверить наличие этого элемента в другом. Я сейчас не принимаю во внимание, что элементом массива может быть массив или объект. К слову, объекты придется сравнивать по значению (как и массивы).

1. Идешь циклом по новому массиву
2. Смотришь, если ли такой элемент в старом массиве
3. Если есть и в той же позиции, идешь дальше
4. Если нет, добавляешь
5. Если отличается позиция перемещаешь
6. Останется отсечь элементы кот. остались в старом массиве, но нет в новом

На первый взгляд можно сделать за один проход по новому массиву (с доп. массивами индексов). Могу ошибаться.

upd: в пыхе, кстати есть http://php.net/manual/ru/function.levenshtein.php и http://www.php.net/manual/ru/function.similar-text.php

upd2: А вот левенштейн на js