min cost string conversion Algorithm
Regular expressions are used in search engines, search and replace dialogs of word CPUs and text editors, in text processing utility such as sed and AWK and in lexical analysis. A regular expression (shortened as regex or regexp; also referred to as rational expression) is a sequence of characters that specify a search shape.
Regular expressions originated in 1951, when mathematician Stephen Cole Kleene described regular languages use his mathematical notation named regular events. Other early implementations of shape matching include the SNOBOL language, which make not use regular expressions, but instead its own shape matching concepts. In the late 2010s, several company started to offer hardware, FPGA, GPU implementations of PCRE compatible regex engines that are faster compared to CPU implementations.
"""
Algorithm for calculating the most cost-efficient sequence for converting one string into another.
The only allowed operations are
---Copy character with cost cC
---Replace character with cost cR
---Delete character with cost cD
---Insert character with cost cI
"""
def compute_transform_tables(X, Y, cC, cR, cD, cI):
X = list(X)
Y = list(Y)
m = len(X)
n = len(Y)
costs = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
ops = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(1, m + 1):
costs[i][0] = i * cD
ops[i][0] = "D%c" % X[i - 1]
for i in range(1, n + 1):
costs[0][i] = i * cI
ops[0][i] = "I%c" % Y[i - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
costs[i][j] = costs[i - 1][j - 1] + cC
ops[i][j] = "C%c" % X[i - 1]
else:
costs[i][j] = costs[i - 1][j - 1] + cR
ops[i][j] = "R%c" % X[i - 1] + str(Y[j - 1])
if costs[i - 1][j] + cD < costs[i][j]:
costs[i][j] = costs[i - 1][j] + cD
ops[i][j] = "D%c" % X[i - 1]
if costs[i][j - 1] + cI < costs[i][j]:
costs[i][j] = costs[i][j - 1] + cI
ops[i][j] = "I%c" % Y[j - 1]
return costs, ops
def assemble_transformation(ops, i, j):
if i == 0 and j == 0:
seq = []
return seq
else:
if ops[i][j][0] == "C" or ops[i][j][0] == "R":
seq = assemble_transformation(ops, i - 1, j - 1)
seq.append(ops[i][j])
return seq
elif ops[i][j][0] == "D":
seq = assemble_transformation(ops, i - 1, j)
seq.append(ops[i][j])
return seq
else:
seq = assemble_transformation(ops, i, j - 1)
seq.append(ops[i][j])
return seq
if __name__ == "__main__":
_, operations = compute_transform_tables("Python", "Algorithms", -1, 1, 2, 2)
m = len(operations)
n = len(operations[0])
sequence = assemble_transformation(operations, m - 1, n - 1)
string = list("Python")
i = 0
cost = 0
with open("min_cost.txt", "w") as file:
for op in sequence:
print("".join(string))
if op[0] == "C":
file.write("%-16s" % "Copy %c" % op[1])
file.write("\t\t\t" + "".join(string))
file.write("\r\n")
cost -= 1
elif op[0] == "R":
string[i] = op[2]
file.write("%-16s" % ("Replace %c" % op[1] + " with " + str(op[2])))
file.write("\t\t" + "".join(string))
file.write("\r\n")
cost += 1
elif op[0] == "D":
string.pop(i)
file.write("%-16s" % "Delete %c" % op[1])
file.write("\t\t\t" + "".join(string))
file.write("\r\n")
cost += 2
else:
string.insert(i, op[1])
file.write("%-16s" % "Insert %c" % op[1])
file.write("\t\t\t" + "".join(string))
file.write("\r\n")
cost += 2
i += 1
print("".join(string))
print("Cost: ", cost)
file.write("\r\nMinimum cost: " + str(cost))
