Show HN: टेक्स्ट एडिटिंग के लिए Transductive रेगुलर एक्सप्रेशन

 (github.com/c0stya)
1 पॉइंट द्वारा GN⁺ 2025-02-09 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • TRRE रेगुलर एक्सप्रेशन में टेक्स्ट ट्रांसफॉर्मेशन को सीधे व्यक्त करने वाला : ऑपरेटर जोड़ने वाला language extension है, और इसे प्रयोग करने के लिए grep -E जैसा CLI tool trre उपलब्ध है
  • इसका मूल रूप transductive pair है, जैसे a:b, जो input pattern को output pattern में बदलता है; deletion को x: और insertion को :x की तरह empty string के साथ transformation के रूप में व्यक्त किया जाता है
  • सामान्य रेगुलर एक्सप्रेशन की तरह alternative selection, repetition और character range transformation इस्तेमाल किए जा सकते हैं, और cat:dog, [a:A-z:Z], Caesar cipher जैसे examples शामिल हैं
  • अंदरूनी implementation सामान्य रेगुलर एक्सप्रेशन के FSA के बजाय input-output pairs संभालने वाला Finite State Transducer(FST) बनाता है, और experimental on-the-fly determinization भी support करता है
  • अभी pre-built binaries नहीं हैं और इसे खुद build करना पड़ता है; DFT stabilization, full Unicode support, ERE features completion, efficient range handling आदि TODO में बचे हैं

TRRE जिस समस्या को हल करना चाहता है

  • सामान्य रेगुलर एक्सप्रेशन टेक्स्ट में pattern खोजने के लिए उपयोगी हैं, लेकिन text editing में group handling logic post-processing जैसा काम करता है और जटिल हो सकता है
  • TRRE pattern matching और text modification को एक ही expression में डालने के लिए regular expression language को extend करता है
  • मुख्य syntax pattern-to-match:pattern-to-generate के रूप में है, और सबसे सरल example a:b है, जो a को b में बदलता है
  • CLI tool trre इस concept को दिखाने वाली implementation है और grep -E जैसा feel देकर काम करता है

बेसिक transformation syntax

  • string substitution को cat:dog की तरह लिखा जाता है
    • echo 'cat' | ./trre 'cat:dog' dog output करता है
    • (c:d)(a:o)(t:g) की तरह character-level transformation से भी वही result बनाया जा सकता है
  • sed की तरह string के अंदर सभी matches को बदलने के लिए इस्तेमाल किया जा सकता है
    • Mary had a little lamb. पर lamb:cat apply करने से Mary had a little cat. बनता है
  • Deletion को right side खाली रखकर string_to_delete: के रूप में व्यक्त किया जाता है
    • (x:)or, xor से x हटाकर or बनाता है
    • a: default scan mode में सभी a को empty symbol में बदलकर हटा देता है
    • [aie]: की तरह bracket expression का उपयोग करके कई characters हटाए जा सकते हैं
  • Insertion को left side खाली रखकर :string_to_insert के रूप में व्यक्त किया जाता है
    • (:x)or, or के आगे x डालकर xor बनाता है
    • had a (:little )lamb context के अंदर little insert करता है

रेगुलर एक्सप्रेशन पर transformations

  • TRRE सामान्य रेगुलर एक्सप्रेशन की तरह | का उपयोग करके alternative selection support करता है
    • (c:b)at|(d:h)og, cat dog को bat hog में बदलता है
  • repetition operators भी transformations पर apply किए जा सकते हैं
    • (cat:dog)*, catcatcat को dogdogdog में बदलता है
    • default scan mode में केवल cat:dog भी बार-बार apply होकर वही result बना सकता है
  • left pattern में repetition इस्तेमाल करने पर कई inputs consume करके उन्हें एक output में बदला जा सकता है
    • (cat)*:dog, catcatcat को dog में बदलता है
  • right pattern में * या + इस्तेमाल करने पर infinite loop हो सकता है
    • :a* जैसे expressions से बचना चाहिए
    • finite repetition चाहिए तो :(repeat-10-times){10} की तरह count specify करें

Range transformations और generators

  • character range transformation को [a:A-z:Z] की तरह लिखा जाता है
    • regular expressions को REGULAR EXPRESSIONS में बदला जा सकता है
  • Caesar cipher example शामिल है
    • [a:b-y:zz:a], caesar cipher को dbftbs djqifs में बदलता है
    • [a:zb:a-z:y] इसे फिर caesar cipher में वापस बदलता है
  • generator की तरह एक input से कई outputs भी बनाए जा सकते हैं
    • default में possible first match का उपयोग होता है
    • -a option इस्तेमाल करने पर सभी possible outputs generate होते हैं
  • example के तौर पर empty input पर :(0|1){3} apply करने से 000 से 111 तक 3-bit binary sequences बनाए जा सकते हैं
  • :(0|1){,3}? और -ma को साथ इस्तेमाल करने पर length 3 या उससे कम के subset-form outputs generate होते हैं

Language spec और operator precedence

  • अनौपचारिक रूप से TRRE को pattern-to-match:pattern-to-generate pairs के रूप में define किया गया है
  • left pattern-to-match string या regular expression हो सकता है
  • right pattern-to-generate आम तौर पर string होता है, लेकिन regular expression भी हो सकता है
  • : operator को फिलहाल non-associative माना जाता है, और TRRE:TRRE रूप syntax के हिसाब से allow नहीं है
    • इस रूप का स्वाभाविक अर्थ TRRE द्वारा define किए गए relations का composition है, लेकिन complexity बढ़ सकती है इसलिए अभी exclude किया गया है
  • operator precedence high से low क्रम में इस तरह है
    • escape character \
    • bracket expression []
    • grouping ()
    • repetition * + ? {m,n}
    • concatenation
    • Transduction :
    • alternative selection |

Modes और greediness

  • trre दो modes support करता है
    • Scan Mode: default mode है और transformations को sequentially apply करता है
    • Match Mode: -m flag इस्तेमाल करता है और check करता है कि पूरी string expression से match होती है या नहीं
  • -a option सभी possible outputs generate करता है
  • ? modifier *, +, {,} operators को non-greedy बनाता है
    • <(.:)*> <cat><dog> से <> output करता है
    • <(.:)*?> उसी input से <><> output करता है
  • tags या brackets के अंदर की content बदलने के examples भी शामिल हैं
    • <(.*?:cat)>, <dog> <mouse> को <cat> <cat> में बदलता है

FST-based implementation और determinization

  • TRRE internally Finite State Transducer(FST) बनाता है
  • FST सामान्य रेगुलर एक्सप्रेशन में इस्तेमाल होने वाले Finite State Automaton(FSA) जैसा है, लेकिन simple strings के बजाय input-output pairs संभालता है
  • TRRE के मुख्य अंतर ये हैं
    • दो regular languages के बीच binary relation define करता है
    • inference में FSA के बजाय FST इस्तेमाल करता है
    • performance के लिए experimental on-the-fly determinization support करता है
  • सामान्य regex engine में determinization non-deterministic automata को deterministic automata में बदलकर input string length के हिसाब से linear-time inference संभव बनाता है
  • TRRE में भी similar approach संभव है, लेकिन सभी non-deterministic transducers NFT को deterministic transducers DFT में नहीं बदला जा सकता
    • एक ही input label वाले दो “bad” cycles हों तो state generation infinite loop में फंस सकता है
    • ऐसे loops detect करने के तरीके हैं, लेकिन cost ज्यादा है

Performance और installation status

  • basic non-deterministic version के लिए simple substitution में sed से थोड़ा धीमा example दिया गया है
    • ./trre '(vodka):(VODKA)': real 0m0.046s
    • sed 's/vodka/VODKA/': real 0m0.024s
  • complex tasks में deterministic version trre_dft के sed से तेज होने का example है
    • sed -e 's/\(.*\)/\U\1/': real 0m0.508s
    • ./trre_dft '[a:A-z:Z]': real 0m0.131s
  • pre-built binaries अभी उपलब्ध नहीं हैं
  • installation में repository clone करने के बाद make && sh test.sh से build और test किया जाता है
  • TODO में ये items बचे हैं
    • stable DFT version
    • full Unicode support
    • ERE features completion
      • [] के अंदर negation ^
      • character classes
      • $^ anchor symbols
    • efficient range handling

संदर्भित approaches

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-02-09
Hacker News टिप्पणियां

  • यह देखना दिलचस्प होगा कि यह project कहां जाता है। हालांकि operator precedence अप्राकृतिक लगता है, और लगता है इस thread में बाकी लोगों को भी कुछ ऐसा ही महसूस हुआ
    cat:dog को स्वाभाविक रूप से ca(t:d)og नहीं, बल्कि (cat):(dog) जैसा मानने की उम्मीद होती है

    • कई मायनों में दिलचस्प idea है
      मुझे भी यह बात उलझाने वाली लगी कि cat:dog को (cat):(dog) नहीं बल्कि ca(t:d)og की तरह parse किया जाता है, लेकिन जब यह याद आया कि हम सब regex का थोड़ा गलत इस्तेमाल कर रहे हैं, तो बात समझ में आई। regex को “मूल रूप से” matcher नहीं, बल्कि string generator के रूप में देखना चाहिए, इसलिए cat|dog को औपचारिक रूप से {catog,cadog} जैसे set में expand होता माना जा सकता है
      matching में इस string set को किसी बड़े text के against substring matching कर देना होता है। समस्या यह है कि असल regex engines में से ज्यादातर इस तरह काम नहीं करते, और अपेक्षाओं से मेल खाने या efficiency के लिए कई अजीब व्यवहार करते हैं
      अलग-अलग regex tools आजमाने पर (cat)|(dog) या (cat)|(dog)|(ca[td]og) जैसी variations निकलती हैं। इसलिए ज्यादा formal नजरिए से देखें तो cat:dog का ca(t:d)og बनाना सही है, न कि (cat):(dog)। लेकिन दशकों से regex को user expectations के हिसाब से matching tool की तरह misuse करने के अनुभव के कारण अब हर कोई जिस expression को replace करना चाहता है, उसके चारों ओर parentheses लगा देता है
      यह proposal दिलचस्प और अच्छी तरह design किया गया है, लेकिन अंत में यह regex को उसके मूल generator model में वापस ले जाने जैसा लगता है। समस्या grammar से ज्यादा tools की तरफ है
      मैंने पहले इस field के आसपास काम किया है, और अगर आपने regex को string set generator के रूप में कभी नहीं सोचा है, तो यहां खेलकर देख सकते हैं: https://onlinestringtools.com/generate-string-from-regex
      हालांकि ऐसे generation tools का behavior भी बहुत specific होता है। जिन tools का मैं इस्तेमाल करता था, उनमें closures आदि पर constraints specify करके generator को सीमित करने के कई तरीके थे
    • feedback के लिए धन्यवाद, और precedence पर मैं भी विचार कर रहा हूं, इसलिए यह बदल सकता है
      अगर इसे concatenation के बाद तक टाल दें, तो दूसरी समस्याएं पैदा हो सकती हैं। उदाहरण के लिए non-associative : में cat:dog:mouse illegal होना पड़ सकता है, लेकिन इसे कैसे संभालना है, इस पर मुझे यकीन नहीं है
      मौजूदा version में epsilon, यानी खाली string, insert की जाती है। उदाहरण के लिए हर दूसरे character को छोड़ते हुए हटाने के लिए technically .(.:eps) यानी ..: चला सकते हैं
      echo 'abcde' | ./trre '..:' का result 'ace' है
      दरअसल : composition का अर्थ regular relations की composition भी हो सकता है, लेकिन फिलहाल मुझे यह बहुत complex लगा
    • range transformation भी similar है। [a:A-z:Z] के बजाय [a-z:A-Z] बेहतर है, और [a:b-y:zz:a] के बजाय [a-y:b-z;z:a] जैसी form propose करना चाहूंगा

  • अगर आपकी रुचि finite-state transducers और संबंधित tools में है, तो XFST(Xerox Finite-State Transducer) देखने लायक है। computational linguistics applications में इसका इस्तेमाल 20 साल से ज्यादा समय से होता आ रहा है
    PARC के एक Finnish researcher UT की class में आए थे और उन्होंने FST से Finnish morphology handle करने का तरीका दिखाया था, जो देखने में भी काफी impressive था

    • मैं भी इसी का mention करने वाला था। Kaplan paper link: https://aclanthology.org/J94-3001.pdf
      PARC में हुए काम को explain करता है
    • http://hfst.github.io/ XFST का modern open source version है। यह foma और OpenFst को cover करता है, और संभवतः trre जो करता है और उससे भी अधिक लगभग सब कुछ कर सकता है
    • Pynini में भी interest हो सकता है। यह OpenFst का Python wrapper है और इसमें usability के लिए कई extra features जोड़े गए हैं
      OpenFst transducers के लिए वाकई शानदार library है। Johns Hopkins आदि द्वारा assignments के रूप में बनाए गए Pynini usage tutorials भी अच्छे हैं
      [1] https://www.openfst.org/twiki/bin/view/GRM/Pynini
      [2] https://www.openfst.org/

  • अगर आप standard regex के alternatives ढूंढ रहे हैं, खासकर जब group logic कठिन लगता हो या maintainable expressions चाहिए हों, तो Rosie Pattern Language उपयुक्त हो सकती है
    https://gitlab.com/rosie-pattern-language/rosie/-/blob/maste...
    https://rosie-lang.org/about/

  • शानदार। मैंने लगभग 1997 में computer science का Diplom thesis finite-state transducers पर लिखा था, और यह जितना लगता था उससे कहीं कम trivial था
    assignment यह था कि जहां संभव हो composition और DFA implement किया जाए, और composed transducers भी शामिल थे। यह “finite-state transducers का algebra” था और use case morphology था। topic को काफी underestimate किया गया था, इसलिए मुझे बीच में ही खत्म करना पड़ा। इसलिए respect
    grammar के बारे में, सच में यह जानना चाहूंगा कि क्या आप चाहते हैं कि : concatenation ab से ज्यादा tightly bind करे

    • 2000s की शुरुआत में bioinformatics में OpenFST इस्तेमाल किया था। खेलने में मजेदार था, लेकिन मेरे काम के लिए अंततः useful नहीं रहा
      20 साल बाद भी project जारी है, यह देखकर अच्छा लगा: https://www.openfst.org/twiki/bin/view/FST/WebHome
    • graduation को practically “क्या आप regex को काफी जोर से handle कर सकते हैं” पर दांव लगाना बहुत bold choice है
    • सही है। transducers बहुत पुराना topic हैं। किसी वजह से वे regex की तरह किसी specific language से strongly connected नहीं हुए
      : को concatenation से ज्यादा tightly bind करना चाहिए या नहीं, इस पर अभी मुझे यकीन नहीं है। करीब 100 examples देखकर मुझे current approach, यानी : का . से lower precedence होना, ज्यादा natural लगा, लेकिन code में literally सिर्फ एक number बदलने से यह change हो सकता है। इसलिए इसे यहां post किया है, और असली feedback चाहिए

  • जिस पल आप किसी तरह का structural substitution करना चाहते हैं, यह तरीका पर्याप्त नहीं लगता। उदाहरण के लिए, कभी-कभी s/"([^"]*)"/'$1'/ जैसा कुछ करना होता है
    इसके अलावा, अगर [^"] में से ['] से match होने वाली चीज़ को \' में बदल सकें, तो यह और उपयोगी लगेगा
    अधिक सामान्य रूप से, regex match result के लिए असल में एक parse tree define करता है, इसलिए उस tree पर ज्यादा सामान्य transformations कर पाना उपयोगी होगा

    • अगर मैंने सही समझा है, तो यह ttre expression आपका काम करता है:
      ":'(':(\\')|[^"'])*":'
    • अगर मैंने सही समझा है, तो आप "..." block के अंदर की content बदलना चाहते हैं और quotes को single quotes ' में बदलना चाहते हैं
      यह expression ऐसा कर सकता है:
      echo '"hello world" "hello again!"' | ./trre "\":'.+?:-\":'"
      result है '-' '-'
      यानी ".+?:-" expression "" के अंदर के text को - symbol से replace करते हुए साथ-साथ आसपास के quotes भी बदल देता है। question mark का मतलब non-greedy mode है

  • ऐसा लगता है कि पूरा project इस दावे पर टिका है कि “regex text में patterns ढूंढने के लिए शानदार tools हैं, लेकिन text editing के लिए हमेशा unnatural लगे”, मगर कोई example ही नहीं है
    मुझे समझ नहीं आता कि editing के लिए regex unnatural क्यों है। यहां editing से क्या मतलब है, यह भी नहीं पता, और लोग groups में कठिनाई क्यों झेलते हैं, यह भी नहीं समझ आता
    इस project में syntax examples बहुत हैं, लेकिन यह सामान्य regex से बेहतर क्यों है, समझ नहीं आता। अगर कुछ examples हों कि “basic regex version यह है, मेरा version यह है, और इसलिए यह आसान हो जाता है”, तो शायद project समझ आ जाए

    • मेरी नजर में regex आम तौर पर एक बार लिखो और फिर दोबारा ठीक न करो वाली चीज ज्यादा होता है। उससे आगे देखने वाला prototype बनाना इस field के बेहतर भविष्य को explore करने का अच्छा तरीका है
    • वाजिब point है। सबसे स्पष्ट example तब है जब सिर्फ context के अंदर बदलना जरूरी हो
      उदाहरण के लिए, x और z के बीच मौजूद सिर्फ y को Y में बदलना हो, तो Python में लगभग ऐसे करेंगे:
      pattern = r'(x)y(z)'
      replacement = r'\1Y\2'
      result = re.sub(pattern, replacement, text)
      मैं इसे xy:Yz pattern से replace करना चाहता हूं:
      result = re.trre('xy:Yz', text)
      अगर x, z ज्यादा complex patterns हों या खुद regex हों, तो यह approach ज्यादा सुविधाजनक हो सकती है
    • सही बात यह है कि regex अकेले editing functionality नहीं देता। groups तो हैं, लेकिन उन groups को combine करने के लिए sed जैसी दूसरी language इस्तेमाल करनी पड़ती है
    • बात substitution की है। author के syntax में substitution को express करना, सचमुच type करना, आसान है
      अच्छा project है

  • C code पढ़ना वाकई मजेदार है। बहुत अच्छा है, और अभी पढ़ रहा हूं
    बस एक छोटा comment: README में theory.pdf link broken है। PDF docs/ directory में है, इसलिए URL में बस docs/ शामिल करना होगा

    • feedback और typo बताने के लिए धन्यवाद। ठीक कर दिया। सच कहूं तो मेरी C skills काफी rusty हैं, इसलिए थोड़ा nervous हूं

  • लिखा है कि right-hand side में * या + इस्तेमाल करने से infinite loop हो सकता है, इसलिए बचें; तो इसे सीधे ban क्यों नहीं कर देते?
    समझता हूं कि grammar spec ज्यादा मुश्किल हो जाएगा, लेकिन इसे बनाए रखने की कोई अच्छी वजह नहीं दिखती

    • वाजिब point है और मैं सहमत हूं। अभी के लिए इसे disable करना बेहतर होगा
      असली वजह यह थी कि मैं transducer composition नाम का एक मजेदार operation implement करना चाहता था। strings पर simple operations करके trre को filter की तरह compose किया जा सकता है, लेकिन अभी इसे पूरा नहीं कर पाया। इसलिए आपका point सही है

  • बढ़िया exploration है, लेकिन असल में यह क्यों बेहतर है, इसके examples कम हैं। हालांकि हो सकता है मैं regex का बहुत लंबे समय से आदी हो गया हूं
    उदाहरण के लिए, trre का (cat):(dog) s/cat/dog से क्यों बेहतर है, या (x:)or s/xor/or से कैसे बेहतर है, यह नहीं समझ आता। लगभग सभी examples मेरे दिमाग में तुलनात्मक रूप से आसान regex से map हो जाते हैं
    अगर कोई core advantage है, तो शायद वह group logic की तरफ होगा, इसलिए examples भी उसी पर focus करें तो अच्छा होगा। basic syntax समझाने से पहले ही यह बताना बेहतर लगता है कि यह बेहतर choice क्यों है
    Caesar cipher example में “इसे reverse direction में apply करो” feature की बहुत जरूरत लगती है। कई text substitutions में यह common request है, और इस example में खास तौर पर साफ दिखता है। programmer का दिमाग तुरंत चिल्लाता है, “एक ही logic दो बार क्यों express करनी पड़े?”
    अभी नहीं पता कि यह useful है या नहीं, लेकिन लंबे समय से जमे status quo के alternatives explore करना शानदार है। आम तौर पर ऐसे प्रयासों के सफल न होने की संभावना भी बड़ी होती है, फिर भी exploration अपने-आप में देखने लायक है

  • स्पेसिफिकेशन काफ़ी अधूरा लगता है। पहला उदाहरण ही अजीब है:
    $ echo 'cat' | trre 'c:da:ot:g'
    dog
    समझ नहीं आता कि यहाँ क्या हो रहा है। syntax इस तरह दिया है:
    TRRE <- TRRE* TRRE|TRRE TRRE.TRRE
    TRRE <- REGEX REGEX:REGEX
    यहाँ parse tree क्या है? c, da में क्यों नहीं बदलता? या फिर c हटकर da, ot में क्यों नहीं बदलता?
    group operator की तुलना में ज़्यादा intuitive search/replace semantics देने का idea अच्छा है। MS-DOS के दौर में ren .log .txt जैसा कुछ कर सकते थे और वह काम करता था; modern bash-style सोच से यह बेतुका लगता है, लेकिन देखते ही intent बहुत साफ़ था

    • यह operator precedence और tokenization की समस्या है। इस language में token single character है, और characters के बीच एक invisible operator होता है
      अगर उस operator को explicitly ~ कहें, तो example ऐसा दिखेगा:
      $ echo 'cat' | trre 'c:d~a:o~t:g'
      dog
      अनावश्यक parentheses डालें तो ऐसा होगा:
      $ echo 'cat' | trre '(c:d)~(a:o)~(t:g)'
      dog
    • grammar की specification अधूरी है। पूरी grammar ज़्यादा complex है। current version शायद docs से हटा देना चाहिए, क्योंकि अभी यह वाकई confusion पैदा कर रहा है
      c, da में क्यों नहीं बदलता, यह पूरा precedence की वजह से है। इस चर्चा को देखकर लगता है कि मैंने गलत precedence चुनी है, और वही confusion पैदा कर रही है
      मौजूदा precedence table इस प्रकार है:
      | 1 | escape character | \ |
      | 2 | bracket expression | [] |
      | 3 | grouping | () |
      | 4 | single-character ERE repetition | * + ? {m,n} |
      | 5 | transformation | : |
      | 6 | concatenation | . (implicit) |
      | 8 | alternation | | |
      इसलिए : की binding . यानी implicit concatenation से ज़्यादा मजबूत है
    • सही है, specification अधूरी है। deletion example दिखाता है कि empty string भी REGEX हो सकती है। तब असल में माना जा सकता है कि किसी भी position पर जितनी चाहें उतनी empty string regexes शामिल हैं, इसलिए parse अनंत संख्या में हो जाते हैं
      इसके बजाय अगर requirement रखें कि regex खाली नहीं होनी चाहिए, तो deletion example टूट जाता है, लेकिन ambiguity concatenation की तरफ़ चली जाती है। यानी ambiguity रहती है कि यह (((c:d)(a:o))(t:g)) है या ((c:d)((a:o)(d:g)))। associativity मान लें तो यह अंतर शायद मायने नहीं रखेगा
    • behavior के लिहाज़ से यह c:d, a: यानी nothing, और ot:g जैसा लगता है
      लेकिन दोबारा पढ़ने पर यह सच में confusing है, और theoretical रूप से आपत्ति सही है। repository पढ़ने के बाद तो मुझे भी लगने लगा कि c को da में बदलना चाहिए, लेकिन पक्का नहीं हूँ