Jakub
Add fuzzy near-match suggestions for numeric columns
fe0d1b4
Raw History Blame Contribute Delete
17.3 kB
"""Core comparison logic.
Algorithm
---------
1. For every ``ColumnMapping`` in the config, normalise the corresponding
column in both tables according to its declared type (text / number / date).
2. Stringfy each normalised column; replace every NaN / NaT with a fixed
sentinel so that two missing values on the *same* key position still
compare as equal.
3. Concatenate all per-column key strings with a null-byte separator into one
composite key per row.
4. Count-aware multiset match: for each composite key count how many copies
exist in B, then within each group of identical keys in A number them
0, 1, 2 … with ``groupby.cumcount()``. A row matches only when its
within-group index is strictly less than the count available in B.
Still O(n + m) β€” only hash-maps and vectorised comparisons.
"""
from __future__ import annotations
from collections import defaultdict
from dataclasses import dataclass, field
import numpy as np
import pandas as pd
from table_comparator.config import ColumnMapping, ComparisonConfig
# Sentinel that replaces every NaN / NaT / pd.NA before hashing.
# Uses null bytes so it cannot collide with real user data.
_NULL_SENTINEL = "\x00NULL\x00"
# Separator between the individual key components.
_KEY_SEP = "\x00\x00"
# ---------------------------------------------------------------------------
# Result container
# ---------------------------------------------------------------------------
@dataclass
class NearMatch:
"""A candidate near-match between an unmatched A row and an unmatched B row."""
row_a: int # 1-based row number in A
row_b: int # 1-based row number in B
diffs: dict[str, float] # column_a name -> signed difference (a_val - b_val)
def _with_row_number(df: pd.DataFrame, mask: pd.Series) -> pd.DataFrame:
"""Return filtered rows with a leading 1-based ``Row`` column."""
out = df[mask].copy()
out.insert(0, "Row", out.index + 1)
return out.reset_index(drop=True)
@dataclass
class ComparisonResult:
"""Outcome of a single comparison run."""
df_a: pd.DataFrame # original Table A (all columns)
matched_mask: pd.Series # boolean; True β†’ row exists in B
df_b: pd.DataFrame # original Table B (all columns)
matched_mask_b: pd.Series # boolean; True β†’ row exists in A
config: ComparisonConfig
warnings: list[str] = field(default_factory=list)
near_matches: list[NearMatch] = field(default_factory=list)
# ------------------------------------------------------------------
# A-side convenience views
# ------------------------------------------------------------------
@property
def matched(self) -> pd.DataFrame:
"""Rows from A that have a match in B (with 1-based Row column)."""
return _with_row_number(self.df_a, self.matched_mask)
@property
def unmatched(self) -> pd.DataFrame:
"""Rows from A that have NO match in B (with 1-based Row column)."""
return _with_row_number(self.df_a, ~self.matched_mask)
@property
def total(self) -> int:
return len(self.df_a)
@property
def match_count(self) -> int:
return int(self.matched_mask.sum())
@property
def unmatch_count(self) -> int:
return self.total - self.match_count
# ------------------------------------------------------------------
# B-side convenience views
# ------------------------------------------------------------------
@property
def matched_b(self) -> pd.DataFrame:
"""Rows from B that have a match in A (with 1-based Row column)."""
return _with_row_number(self.df_b, self.matched_mask_b)
@property
def unmatched_b(self) -> pd.DataFrame:
"""Rows from B that have NO match in A (with 1-based Row column)."""
return _with_row_number(self.df_b, ~self.matched_mask_b)
@property
def total_b(self) -> int:
return len(self.df_b)
@property
def match_count_b(self) -> int:
return int(self.matched_mask_b.sum())
@property
def unmatch_count_b(self) -> int:
return self.total_b - self.match_count_b
# ---------------------------------------------------------------------------
# Normalisation helpers
# ---------------------------------------------------------------------------
def _strip_thousand_separators(series: pd.Series, decimal_separator: str = ".") -> pd.Series:
"""Remove thousand separators from number strings to enable parsing.
Handles multiple locale formats by using an explicit decimal separator:
- US/UK format: 1,234.56 (comma thousands, dot decimal) β†’ decimal_separator="."
- European format: 1.234,56 or 1 234,56 (dot/space thousands, comma decimal) β†’ decimal_separator=","
- Swiss format: 1'234.56 (apostrophe thousands, dot decimal) β†’ decimal_separator="."
Args:
series: The pandas Series containing number strings
decimal_separator: The character used as decimal separator ("." or ",")
Strategy:
1. Convert to string
2. Remove all thousand separators (common separators that are NOT the decimal separator)
3. Normalize decimal separator to dot for pd.to_numeric
"""
# Convert to string, preserving nulls
str_series = series.astype("string")
def clean_number(val: str) -> str:
if pd.isna(val) or val == "<NA>":
return val
val = val.strip()
if not val:
return val
# Define common thousand separators
thousand_separators = [",", ".", " ", "'", "_"]
# Remove the decimal separator from the list of thousand separators
if decimal_separator in thousand_separators:
thousand_separators.remove(decimal_separator)
# Remove all thousand separators
cleaned = val
for sep in thousand_separators:
cleaned = cleaned.replace(sep, "")
# Normalize decimal separator to dot (required by pd.to_numeric)
if decimal_separator == ",":
cleaned = cleaned.replace(",", ".")
return cleaned
return str_series.apply(clean_number)
def _normalize(series: pd.Series, mapping: ColumnMapping, side: str) -> pd.Series:
"""Normalise one column according to its declared type.
*side* is ``"a"`` or ``"b"`` β€” used to pick the correct date format.
"""
if mapping.col_type == "text":
# Use pandas StringDtype so that str methods preserve NA
result = series.astype("string").str.strip()
if not mapping.case_sensitive:
result = result.str.lower()
return result
if mapping.col_type == "number":
# Strip thousand separators before parsing to handle locale formats
decimal_sep = mapping.decimal_separator_a if side == "a" else mapping.decimal_separator_b
cleaned = _strip_thousand_separators(series, decimal_sep)
result = pd.to_numeric(cleaned, errors="coerce")
if mapping.rounding is not None:
result = result.round(mapping.rounding)
# Cast to float64 unconditionally. to_numeric returns int64 when all
# values parse cleanly but float64 when any value coerces to NaN.
# The two dtypes stringify differently ("100" vs "100.0"), which would
# break key matching between the two sides.
return result.astype("float64")
if mapping.col_type == "date":
fmt = mapping.date_format_a if side == "a" else mapping.date_format_b
return pd.to_datetime(series, format=fmt, errors="coerce")
return series # fallback – should not happen after validation
def _to_key_str(series: pd.Series) -> pd.Series:
"""Stringify a normalised series; replace every null with *_NULL_SENTINEL*.
This makes NaN == NaN for key purposes while keeping everything vectorised.
"""
null_mask = series.isna()
result = series.astype(str)
result.loc[null_mask] = _NULL_SENTINEL
return result
# ---------------------------------------------------------------------------
# Near-match search
# ---------------------------------------------------------------------------
def _find_near_matches(
config: ComparisonConfig,
norm_columns_a: dict[str, pd.Series],
norm_columns_b: dict[str, pd.Series],
matched_mask: pd.Series,
matched_mask_b: pd.Series,
) -> list[NearMatch]:
"""Find candidate near-matches among unmatched rows.
For each unmatched A row, find all unmatched B rows where:
- all non-numeric mapped columns match exactly (using normalised values)
- every numeric column with a margin has abs(diff) <= margin
Returns a list of NearMatch objects.
"""
# Identify which number columns have a margin configured
margin_mappings: list[ColumnMapping] = [
m for m in config.columns
if m.col_type == "number" and m.margin is not None
]
if not margin_mappings:
return []
# Non-numeric mappings (must match exactly) + numeric without margin
exact_mappings: list[ColumnMapping] = [
m for m in config.columns
if not (m.col_type == "number" and m.margin is not None)
]
# Get unmatched indices
unmatched_idx_a = matched_mask[~matched_mask].index.tolist()
unmatched_idx_b = matched_mask_b[~matched_mask_b].index.tolist()
if not unmatched_idx_a or not unmatched_idx_b:
return []
# Build composite exact-match key for grouping (non-margin columns)
if exact_mappings:
exact_parts_a = []
exact_parts_b = []
for m in exact_mappings:
exact_parts_a.append(
_to_key_str(norm_columns_a[m.column_a]).loc[unmatched_idx_a]
)
exact_parts_b.append(
_to_key_str(norm_columns_b[m.column_b]).loc[unmatched_idx_b]
)
exact_key_a = exact_parts_a[0]
for part in exact_parts_a[1:]:
exact_key_a = exact_key_a + _KEY_SEP + part
exact_key_b = exact_parts_b[0]
for part in exact_parts_b[1:]:
exact_key_b = exact_key_b + _KEY_SEP + part
# Group unmatched B rows by their exact key
b_groups: dict[str, list[int]] = defaultdict(list)
for idx in unmatched_idx_b:
b_groups[exact_key_b.loc[idx]].append(idx)
else:
# All columns are numeric with margin β€” every unmatched B is a candidate
exact_key_a = None
b_groups = None
# Extract numeric values for margin columns
num_vals_a = {
m.column_a: norm_columns_a[m.column_a].loc[unmatched_idx_a]
for m in margin_mappings
}
num_vals_b = {
m.column_a: norm_columns_b[m.column_b].loc[unmatched_idx_b]
for m in margin_mappings
}
results: list[NearMatch] = []
for idx_a in unmatched_idx_a:
# Get candidate B indices
if b_groups is not None:
key = exact_key_a.loc[idx_a]
candidates = b_groups.get(key, [])
else:
candidates = unmatched_idx_b
for idx_b in candidates:
diffs: dict[str, float] = {}
match = True
for m in margin_mappings:
val_a = num_vals_a[m.column_a].loc[idx_a]
val_b = num_vals_b[m.column_a].loc[idx_b]
# If either value is NaN, can't compute a numeric diff
if np.isnan(val_a) or np.isnan(val_b):
match = False
break
diff = val_a - val_b
if abs(diff) > m.margin:
match = False
break
diffs[m.column_a] = diff
if match:
results.append(NearMatch(
row_a=idx_a + 1, # 1-based
row_b=idx_b + 1, # 1-based
diffs=diffs,
))
return results
# ---------------------------------------------------------------------------
# Public API
# ---------------------------------------------------------------------------
def compare(
config: ComparisonConfig,
df_a: pd.DataFrame,
df_b: pd.DataFrame,
) -> ComparisonResult:
"""Check which rows in *df_a* have a matching row in *df_b*.
Matching is defined by the column mappings in *config*: a row in A matches
a row in B when **all** mapped column pairs are equal after normalisation.
Returns a :class:`ComparisonResult` that contains the original Table A,
a boolean mask, and any parse warnings.
"""
if not config.columns:
raise ValueError("No column mappings configured.")
# --- column-existence check -------------------------------------------
for m in config.columns:
if m.column_a not in df_a.columns:
raise ValueError(
f"Column '{m.column_a}' not found in Table A. "
f"Available: {list(df_a.columns)}"
)
if m.column_b not in df_b.columns:
raise ValueError(
f"Column '{m.column_b}' not found in Table B. "
f"Available: {list(df_b.columns)}"
)
warnings: list[str] = []
key_parts_a: list[pd.Series] = []
key_parts_b: list[pd.Series] = []
norm_columns_a: dict[str, pd.Series] = {}
norm_columns_b: dict[str, pd.Series] = {}
for m in config.columns:
orig_a = df_a[m.column_a]
orig_b = df_b[m.column_b]
orig_nulls_a = int(orig_a.isna().sum())
orig_nulls_b = int(orig_b.isna().sum())
norm_a = _normalize(orig_a, m, "a")
norm_b = _normalize(orig_b, m, "b")
# --- warn about values that failed to parse (new nulls) -----------
if m.col_type in ("date", "number"):
label = m.col_type
# Find rows where parsing failed (was not null before, is null after)
failed_a = ~orig_a.isna() & norm_a.isna()
failed_b = ~orig_b.isna() & norm_b.isna()
extra_a = int(failed_a.sum())
extra_b = int(failed_b.sum())
if extra_a > 0:
# Get row indices and values that failed to parse
failed_indices = failed_a[failed_a].index.tolist()
failed_values = orig_a[failed_a].tolist()
# Limit examples to first 10 to avoid overwhelming output
max_examples = 10
examples = []
for idx, val in zip(failed_indices[:max_examples], failed_values[:max_examples]):
examples.append(f" Row {idx}: {repr(val)}")
warning = (
f"Table A '{m.column_a}': {extra_a} value(s) could not be "
f"parsed as {label}:\n" + "\n".join(examples)
)
if extra_a > max_examples:
warning += f"\n ... and {extra_a - max_examples} more"
warnings.append(warning)
if extra_b > 0:
# Get row indices and values that failed to parse
failed_indices = failed_b[failed_b].index.tolist()
failed_values = orig_b[failed_b].tolist()
# Limit examples to first 10 to avoid overwhelming output
max_examples = 10
examples = []
for idx, val in zip(failed_indices[:max_examples], failed_values[:max_examples]):
examples.append(f" Row {idx}: {repr(val)}")
warning = (
f"Table B '{m.column_b}': {extra_b} value(s) could not be "
f"parsed as {label}:\n" + "\n".join(examples)
)
if extra_b > max_examples:
warning += f"\n ... and {extra_b - max_examples} more"
warnings.append(warning)
norm_columns_a[m.column_a] = norm_a
norm_columns_b[m.column_b] = norm_b
key_parts_a.append(_to_key_str(norm_a))
key_parts_b.append(_to_key_str(norm_b))
# --- build composite key (concat with separator) ----------------------
key_a = key_parts_a[0]
for part in key_parts_a[1:]:
key_a = key_a + _KEY_SEP + part
key_b = key_parts_b[0]
for part in key_parts_b[1:]:
key_b = key_b + _KEY_SEP + part
# --- count-aware multiset match (A→B) -----------------------------------
# How many copies of each key are available in B.
count_b = key_b.value_counts()
# Within each group of identical keys in A, assign indices 0, 1, 2 …
cumcount_a = key_a.groupby(key_a).cumcount()
# A row matches only if its within-group index < copies available in B.
matched_mask = cumcount_a < key_a.map(count_b).fillna(0).astype(int)
# --- count-aware multiset match (B→A) -----------------------------------
count_a = key_a.value_counts()
cumcount_b = key_b.groupby(key_b).cumcount()
matched_mask_b = cumcount_b < key_b.map(count_a).fillna(0).astype(int)
near_matches = _find_near_matches(
config, norm_columns_a, norm_columns_b, matched_mask, matched_mask_b,
)
return ComparisonResult(
df_a=df_a,
matched_mask=matched_mask,
df_b=df_b,
matched_mask_b=matched_mask_b,
config=config,
warnings=warnings,
near_matches=near_matches,
)