Karaby: 1 версия импортирована

2025-07-27T15:38:10Z

1 версия импортирована

← Предыдущая версия	Версия от 15:38, 27 июля 2025
(нет различий)

Буквица>D6194c-1cc: D6194c-1cc переименовал страницу Модуль:Песочница/D6194c-1cc/Diff в Модуль:Diff без оставления перенаправления: Публикация модуля из черновика

2023-07-15T21:34:27Z

D6194c-1cc переименовал страницу Модуль:Песочница/D6194c-1cc/Diff в Модуль:Diff без оставления перенаправления: Публикация модуля из черновика

Новая страница

local p = {}

-- TODO: Провести эксперимент с получением таблицы из символов из строки, проверить
-- будет, ли это быстрее, чем сравнение подстрок. Если представление ustring именно UTF-8,
-- то работа с таблицей может быть в теории быстрее (нет необходимости каждый раз обходить
-- всю строку для вычисления позиции символа).
-- Альтернативно подумать над алгоритмом побайтового сравнения, это должно быть быстрее.

-- TODO: Проверить по производительности в strLongestCommonRange() смену большей
-- и меньшей строк местами.

-- TODO: Использовать find с указанием индекса начала поиска в strLongestCommonRange.

function p.strLongestCommonRange(s1, s2, minWindowSize)
-- TODO: Начало и длина вместо диапазонов
if not minWindowSize then
minWindowSize = 0
end
local longestStart1 = 0
local longestEnd1 = 0
local longestStart2 = 0
local longestEnd2 = 0
local currStart = 1
local currEnd = 1 + minWindowSize

local s1Len = mw.ustring.len(s1)
local s2Len = mw.ustring.len(s2)

while currEnd <= s1Len do
local found = false
local subS1
local subS2
local i = 1

subS1 = mw.ustring.sub(s1, currStart, currEnd)
while i + (currEnd - currStart) <= s2Len do
if not found then
subS2 = mw.ustring.sub(s2, i, i + (currEnd - currStart))
if subS1 == subS2 then
found = true
currEnd = currEnd + 1
if currEnd > s1Len then
break
end
else
i = i + 1
end
else
local currEnd2 = i + currEnd - currStart
if mw.ustring.sub(s1, currEnd, currEnd) == mw.ustring.sub(s2, currEnd2, currEnd2) then
currEnd = currEnd + 1
if currEnd > s1Len then
break
end
else
if currEnd - 1 - currStart > s1Len / 2 then
return { currStart, currEnd - 1 }, { i, i + currEnd - 1 - currStart }
end
subS1 = mw.ustring.sub(s1, currStart, currEnd)
if currEnd - 1 - currStart > longestEnd1 - longestStart1 or longestStart1 == 0 then
longestStart1 = currStart
longestEnd1 = currEnd - 1
longestStart2 = i
longestEnd2 = i + (longestEnd1 - longestStart1)
end
found = false
i = i + 1
end
end
end
if found then
if currEnd - 1 - currStart > longestEnd1 - longestStart1 or longestStart1 == 0 then
longestStart1 = currStart
longestEnd1 = currEnd - 1
longestStart2 = i
longestEnd2 = i + (longestEnd1 - longestStart1)
end
end
currStart = currStart + 1
currEnd = currEnd + 1
end

if longestStart1 == 0 then
return nil, nil
end
return { longestStart1, longestEnd1 }, { longestStart2, longestEnd2 }
end

function p.strCommonRangesApprox(s1, s2, limit, s1Offset, s2Offset, ranges)
ranges = ranges or {}
s1Offset = s1Offset or 0
s2Offset = s2Offset or 0

if s1 == '' or s2 == '' then
return ranges
end

local d1, d2 = p.strLongestCommonRange(s1, s2, limit or 0)
if d1 == nil then
return ranges
end
if limit and d1[2] - d1[1] <= limit and d2[2] - d2[1] <= limit then
return ranges
end

if d1[1] > 1 then
p.strCommonRangesApprox(
mw.ustring.sub(s1, 1, d1[1] - 1),
mw.ustring.sub(s2, 1, d2[1] - 1),
limit,
s1Offset,
s2Offset,
ranges)
end

d1[1] = d1[1] + s1Offset
d1[2] = d1[2] + s1Offset

d2[1] = d2[1] + s2Offset
d2[2] = d2[2] + s2Offset

table.insert(ranges, { d1, d2 })

if d1[2] - s1Offset < mw.ustring.len(s1) and d2[2] - s2Offset < mw.ustring.len(s2) then
p.strCommonRangesApprox(
mw.ustring.sub(s1, d1[2] + 1, mw.ustring.len(s1)),
mw.ustring.sub(s2, d2[2] + 1, mw.ustring.len(s2)),
limit,
d1[2], d2[2],
ranges)
end

return ranges
end

function p.strCommonRanges(s1, s2, s1Offset, s2Offset, ranges)
return p.strCommonRangesApprox(s1, s2, nil, s1Offset, s2Offset, ranges)
end

local function tryGetWholeDiff(s1, s2)
local s1Set = (s1 and s1 ~= '')
local s2Set = (s2 and s2 ~= '')
if s1Set and not s2Set then
return {
{
{ 1, mw.ustring.len(s1) },
{ 1, 0 },
},
}
elseif not s1Set and s2Set then
return {
{
{ 1, 0 },
{ 1, mw.ustring.len(s2) },
},
}
elseif (not s1Set and not s2Set) or (s1 == s2) then
return {}
end

return nil
end

local function strDiffRangesNonNil(s1, s2, limit)
local commonSubstrings = p.strCommonRangesApprox(s1, s2, limit)
if table.getn(commonSubstrings) == 0 then
return {
{
{ 1, mw.ustring.len(s1) },
{ 1, mw.ustring.len(s2) },
},
}
end

local diffs = {}

local curr = commonSubstrings[1]
local last1 = 1
local last2 = 1
if curr[1][1] - last1 > 0 or curr[2][1] - last2 > 0 then
table.insert(diffs, {
{ last1, curr[1][1] - last1 },
{ last2, curr[2][1] - last2 },
})
end
last1 = curr[1][2]
last2 = curr[2][2]

for i = 2, table.getn(commonSubstrings) do
curr = commonSubstrings[i]
if curr[1][1] - last1 > 0 and curr[2][1] - last2 > 0 then
if curr[1][1] - last1 > 0 then
last1 = last1 + 1
end
if curr[2][1] - last2 > 0 then
last2 = last2 + 1
end
table.insert(diffs, {
{ last1, curr[1][1] - last1 },
{ last2, curr[2][1] - last2 },
})
end
last1 = curr[1][2]
last2 = curr[2][2]
end

if mw.ustring.len(s1) - last1 > 0 or mw.ustring.len(s2) - last2 > 0 then
table.insert(diffs, {
{ last1 + 1, mw.ustring.len(s1) - last1 },
{ last2 + 1, mw.ustring.len(s2) - last2 },
})
end

return diffs
end

function p.strDiffRanges(s1, s2, limit)
local diffs = tryGetWholeDiff(s1, s2)
if diffs then
return diffs
else
diffs = {}
end

return strDiffRangesNonNil(s1, s2, limit)
end

function p.findCommonFromStart(s1, s2)
if mw.ustring.sub(s1, 1, 1) ~= mw.ustring.sub(s2, 1, 1) then
return nil
end

local s1Len = mw.ustring.len(s1)
local s2Len = mw.ustring.len(s2)
local sLen
if s1Len < s2Len then
sLen = s1Len
else
sLen = s2Len
end
local i = 1
local d = math.floor(sLen / 10)
if d < 1 then
d = 1
end
while i <= sLen do
local s1Start = mw.ustring.sub(s1, i, i + d)
local s2Start = mw.ustring.sub(s2, i, i + d)
if s1Start ~= s2Start then
for j = 1, d do
if mw.ustring.sub(s1Start, j, j) ~= mw.ustring.sub(s2Start, j, j) then
return i + j - 1 - 1
end
end
end
i = i + d
end

return sLen
end

function p.findCommonFromEnd(s1, s2)
local s1Len = mw.ustring.len(s1)
local s2Len = mw.ustring.len(s2)
if mw.ustring.sub(s1, s1Len, s1Len) ~= mw.ustring.sub(s2, s2Len, s2Len) then
return nil
end

local sLen
if s1Len < s2Len then
sLen = s1Len
else
sLen = s2Len
end
local i = 0
local d = math.floor(sLen / 10)
if d < 1 then
d = 1
end
while i <= sLen do
local s1Start = mw.ustring.sub(s1, s1Len - (i + d), s1Len - i)
local s2Start = mw.ustring.sub(s2, s2Len - (i + d), s2Len - i)
if s1Start ~= s2Start then
for j = d, 1, -1 do
if mw.ustring.sub(s1Start, j, j) ~= mw.ustring.sub(s2Start, j, j) then
return i + d - j + 1
end
end
end
i = i + d
end

return sLen
end

-- Symbol from the string in Lua can be obtained only by the sub function,
-- which creates new string with global deduplication. Symbol by symbol
-- comparison is very slow. Diff algorithm is fast on small strings,
-- but on large strings it becomes extremely slowly in Lua.
-- On large strings, approximations are made to ignore minor similarities.
function p.fastStrDiffRanges(s1, s2, accuracyMaxLen)
local diffs = tryGetWholeDiff(s1, s2)
if diffs then
return diffs
end

local limit
local totalLen = s1:len() + s2:len()

local startIndex

if not accuracyMaxLen then
accuracyMaxLen = 300
end
if totalLen > accuracyMaxLen then
startIndex = p.findCommonFromStart(s1, s2)
local endIndex = p.findCommonFromEnd(s1, s2)
if startIndex then
startIndex = startIndex + 1
end
if startIndex or endIndex then
if not endIndex then
endIndex = 0
end
s1 = mw.ustring.sub(s1, startIndex or 1, mw.ustring.len(s1) - endIndex)
s2 = mw.ustring.sub(s2, startIndex or 1, mw.ustring.len(s2) - endIndex)
end
totalLen = s1:len() + s2:len()
if totalLen > accuracyMaxLen then
limit = totalLen - accuracyMaxLen
end
end

diffs = p.strDiffRanges(s1, s2, limit)
if startIndex then
for _, diff in ipairs(diffs) do
diff[1][1] = diff[1][1] + startIndex - 1
diff[2][1] = diff[2][1] + startIndex - 1
end
end
return diffs
end

return p

Модуль:Diff - История изменений

Karaby: 1 версия импортирована

Буквица>D6194c-1cc: D6194c-1cc переименовал страницу Модуль:Песочница/D6194c-1cc/Diff в Модуль:Diff без оставления перенаправления: Публикация модуля из черновика