Asked  7 Months ago    Answers:  5   Viewed   22 times

Note: This is a question about possibilities of modern regex flavors. It's not about the best way to solve this using other methods. It's inspired by an earlier question, but that one is not restricted to regex.

The Problem

In an ASCII "image"/art/map/string like:

....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....

I'd like to find a simple vertical line formation of three Xs:

X
X
X

The number of lines is variable in the image, and the width of each line is variable too.

The Question(s)

With regex (PCRE/PHP, Perl, .NET or similar) is it possible to:

  1. Determine if such a formation exists
  2. Count the number of such formations/match the starting point of them all (4 in the above example)

 Answers

35

Answer to question 1

To answer the first question one could use:

(?xm)                    # ignore comments and whitespace, ^ matches beginning of line
^                        # beginning of line
(?:
    .                    # any character except n
    (?=                  # lookahead
        .*+n            # go to next line
        ( 1?+ . )       # add a character to the 1st capturing group
        .*+n            # next line
        ( 2?+ . )       # add a character to the 2nd capturing group
    )
)*?                      # repeat as few times as needed
X .*+n                  # X on the first line and advance to next line
1?+                     # if 1st capturing group is defined, use it, consuming exactly the same number of characters as on the first line
X .*+n                  # X on the 2nd line and advance to next line
2?+                     # if 2st capturing group is defined, use it, consuming exactly the same number of characters as on the first line
X                        # X on the 3rd line

Online demo

This expression works in Perl, PCRE, Java and should work in .NET.

The expression uses lookaheads with self referencing capturing groups to add a character for every repetition of the lookahead (this is used to "count").

1?+ means if 1 matches (or is defined) consume it, and don't give it back (don't backtrack). In this case it's equivalent to (?(1) 1 ). Which means match 1 if 1 is defined.

polygenelubricants explains this kinds of lookaheads with backreferences very nicely in his answer for How can we match a^n b^n with Java regex?. (He has also written about other impressive tricks for Java regex involving backreferences and lookarounds.)

Answer to question 2

Plain matching

When just using matching and requiring the answer (count) in the number of matches, then the question 2 answer would be:

It can not be directly solved in regex flavors that have a limited lookbehind. While other flavors like Java and .NET could (as for example in m.buettner's .NET solution).

Thus plain regex matches in Perl and PCRE (PHP, etc) cannot directly answer this question in this case.

(Semi?)proof

Assume that no variable length lookbehinds are available.

You have to in some way count the number of characters on a line before an X.
Only way to do that is to match them, and since no variable length lookbehinds are available you have to start the match (at least) at the beginning of the line.
If you start the match at the beginning of a line you can only get at most one match per line.

Since there can be multiple occurrences per line, this would not count them all and would not give a correct answer.

Length/indirect solution

On the other hand if we accept the answer as the length of a match or substitution result, then the 2nd question can be answered in PCRE and Perl (and other flavors).

This solution is based on/inspired by m.buettner's nice "partial PCRE solution".

One could simply replace all matches of the following expression with $3, getting the answer to question two (the number of patterns of interests) as the length of the resulting string.

^
(?:
    (?:                   # match .+? characters
        .
        (?=               # counting the same number on the following two lines
            .*+n
            ( 1?+ . )
            .*+n
            ( 2?+ . )
        )
    )+?
    (?<= X )              # till the above consumes an X
    (?=                   # that matches the following conditions
        .*+n
        1?+
        (?<= X )
        .*+n
        2?+
        (?<= X )
    )
    (?=                   # count the number of matches
        .*+n
        ( 3?+ . )        # the number of matches = length of $3
    )
)*                        # repeat as long as there are matches on this line
.*n?                     # remove the rest of the line

Which in Perl could be written as:

$in =~ s/regex/$3/gmx;
$count = length $in;

Online demo

This expression is similar to the solution to question 1 above, with some modifications to include X in the characters matched in the first lookahead, wrapped with a quantifier and counting number of matches of the quantifier.

Except for direct matches this is as close as it gets (extra code wise besides regex), and could be an acceptable answer to question 2.

Test cases

Some test cases and results for the above solution. Result showing the numerical answer (length of the resulting string) and in parenthesis the resulting string after the substitution(s).

Test #0:
--------------------
X
X
X

result: 1 (X)


Test #1:
--------------------
..X....
..X....
..X....

result: 1 (.)


Test #2:
--------------------
..X.X..
..X.X..
....X..

result: 1 (.)


Test #3:
--------------------
..X....
..X....
...X...

result: 0 ()


Test #4:
--------------------
..X....
...X...
..X....

result: 0 ()


Test #5:
--------------------
....X..
.X..X..
.X.....

result: 0 ()


Test #6:
--------------------
.X..X..
.X.X...
.X.X...

result: 1 (.)


Test #7:
--------------------
.X..X..
.X..X..
.X..X..

result: 2 (.X)


Test #8:
--------------------
XXX
XXX
XXX

result: 3 (XXX)


Test #9:
--------------------
X.X.X
XXXXX
XXXXX
.X.X.

result: 5 (XXXXX)


Test #10:
--------------------
1....X.......
2..X..X...X....
3X.X...X..X.....
4X....XXXXXX.....
5X..XXX...........
6.....X..........
7.........X....X
8..X......X....X....
9..X......X....X....X...
A....X.....
B.X..X..
C.....
XXX
XXX
XXX
.

result: 8 (3458.XXX)
Wednesday, March 31, 2021
 
muaaz
answered 7 Months ago
19

There are a couple of important things to know about bash's [[ ]] construction. The first:

Word splitting and pathname expansion are not performed on the words between the [[ and ]]; tilde expansion, parameter and variable expansion, arithmetic expansion, command substitution, process substitution, and quote removal are performed.

The second thing:

An additional binary operator, ‘=~’, is available,... the string to the right of the operator is considered an extended regular expression and matched accordingly... Any part of the pattern may be quoted to force it to be matched as a string.

Consequently, $v on either side of the =~ will be expanded to the value of that variable, but the result will not be word-split or pathname-expanded. In other words, it's perfectly safe to leave variable expansions unquoted on the left-hand side, but you need to know that variable expansions will happen on the right-hand side.

So if you write: [[ $x =~ [$0-9a-zA-Z] ]], the $0 inside the regex on the right will be expanded before the regex is interpreted, which will probably cause the regex to fail to compile (unless the expansion of $0 ends with a digit or punctuation symbol whose ascii value is less than a digit). If you quote the right-hand side like-so [[ $x =~ "[$0-9a-zA-Z]" ]], then the right-hand side will be treated as an ordinary string, not a regex (and $0 will still be expanded). What you really want in this case is [[ $x =~ [$0-9a-zA-Z] ]]

Similarly, the expression between the [[ and ]] is split into words before the regex is interpreted. So spaces in the regex need to be escaped or quoted. If you wanted to match letters, digits or spaces you could use: [[ $x =~ [0-9a-zA-Z ] ]]. Other characters similarly need to be escaped, like #, which would start a comment if not quoted. Of course, you can put the pattern into a variable:

pat="[0-9a-zA-Z ]"
if [[ $x =~ $pat ]]; then ...

For regexes which contain lots of characters which would need to be escaped or quoted to pass through bash's lexer, many people prefer this style. But beware: In this case, you cannot quote the variable expansion:

# This doesn't work:
if [[ $x =~ "$pat" ]]; then ...

Finally, I think what you are trying to do is to verify that the variable only contains valid characters. The easiest way to do this check is to make sure that it does not contain an invalid character. In other words, an expression like this:

valid='0-9a-zA-Z $%&#' # add almost whatever else you want to allow to the list
if [[ ! $x =~ [^$valid] ]]; then ...

! negates the test, turning it into a "does not match" operator, and a [^...] regex character class means "any character other than ...".

The combination of parameter expansion and regex operators can make bash regular expression syntax "almost readable", but there are still some gotchas. (Aren't there always?) One is that you could not put ] into $valid, even if $valid were quoted, except at the very beginning. (That's a Posix regex rule: if you want to include ] in a character class, it needs to go at the beginning. - can go at the beginning or the end, so if you need both ] and -, you need to start with ] and end with -, leading to the regex "I know what I'm doing" emoticon: [][-])

Thursday, June 3, 2021
 
daniel__
answered 5 Months ago
88

Be Especially Careful with non?ASCII in Python

There are some really subtle issues with how Python deals with, or fails to deal with, non-ASCII in patterns and strings. Worse, these disparities vary substantially according, not just to which version of Python you are using, but also whether you have a “wide build”.

In general, when you’re doing Unicode stuff, Python 3 with a wide build works best and Python 2 with a narrow build works worst, but all combinations are still a pretty far cry far from how Perl regexes work vis?à?vis Unicode. If you’re looking for ???? patterns in Python, you may have to look a bit further afield than its old re module.

The vexing “wide-build” issues have finally been fixed once and for all — provided you use a sufficiently advanced release of Python. Here’s an excerpt from the v3.3 release notes:

Functionality

Changes introduced by PEP 393 are the following:

  • Python now always supports the full range of Unicode codepoints, including non-BMP ones (i.e. from U+0000 to U+10FFFF). The distinction between narrow and wide builds no longer exists and Python now behaves like a wide build, even under Windows.
  • With the death of narrow builds, the problems specific to narrow builds have also been fixed, for example:
    • len() now always returns 1 for non-BMP characters, so len('U0010FFFF') == 1;
    • surrogate pairs are not recombined in string literals, so 'uDBFFuDFFF' != 'U0010FFFF';
    • indexing or slicing non-BMP characters returns the expected value, so 'U0010FFFF'[0] now returns 'U0010FFFF' and not 'uDBFF';
    • all other functions in the standard library now correctly handle non-BMP codepoints.
  • The value of sys.maxunicode is now always 1114111 (0x10FFFF in hexadecimal). The PyUnicode_GetMax() function still returns either 0xFFFF or 0x10FFFF for backward compatibility, and it should not be used with the new Unicode API (see issue 13054).
  • The ./configure flag --with-wide-unicode has been removed.

The Future of Python Regexes

In contrast to what’s currently available in the standard Python distribution’s re library, Matthew Barnett’s regex module for both Python 2 and Python 3 alike is much, much better in pretty much all possible ways and will quite probably replace re eventually. Its particular relevance to your question is that his regex library is far more ???? (i.e. it’s much more Perl?compatible) in every way than re now is, which will make porting Perl regexes to Python easier for you. Because it is a ground?up rewrite (as in from?scratch, not as in hamburger :), it was written with non-ASCII in mind, which re was not.

The regex library therefore much more closely follows the (current) recommendations of UTS#18: Unicode Regular Expressions in how it approaches things. It meets or exceeds the UTS#18 Level 1 requirements in most if not all regards, something you normally have to use the ICU regex library or Perl itself for — or if you are especially courageous, the new Java 7 update to its regexes, as that also conforms to the Level One requirements from UTS#18.

Beyond meeting those Level One requirements, which are all absolutely essential for basic Unicode support, but which are not met by Python’s current re library, the awesome regex library also meets the Level Two requirements for RL2.5 Named Characters (N{...})), RL2.2 Extended Grapheme Clusters (X), and the new RL2.7 on Full Properties from revision 14 of UTS#18.

Matthew’s regex module also does Unicode casefolding so that case insensitive matches work reliably on Unicode, which re does not.

The following is no longer true, because regex now supports full Unicode casefolding, like Perl and Ruby.

One super?tiny difference is that for now, Perl’s case?insensitive patterns use full string?oriented casefolds while his regex module still uses simple single?char?oriented casefolds, but this is something he’s looking into. It’s actually a very hard problem, one which apart from Perl, only Ruby even attempts.

Under full casefolding, this means that (for example) "ß" now correct matches "SS", "ss", "??", "?s" (etc.) when case-insensitive matching is selected. (This is admittedly more important in the Greek script than the Latin one.)

See also the slides or doc source code from my third OSCON2011 talk entitled Unicode Support Shootout: The Good, the Bad, and the (mostly) Ugly for general issues in Unicode support across JavaScript, PHP, Go, Ruby, Python, Java, and Perl. If can’t use either Perl regexes or possibly the ICU regex library (which doesn’t have named captures, alas!), then Matthew’s regex for Python is probably your best shot.


N??? B??? s.?.?. (= s’il vous plaît, et même s’il ne vous plaît pas :) The following unsolicited noncommercial nonadvertisement was not actually put here by the author of the Python regex library. :)

Cool regex Features

The Python regex library has a cornucopeia of superneat features, some of which are found in no other regex system anywhere. These make it very much worth checking out no matter whether you happen to be using it for its ?????ness or its stellar Unicode support.

A few of this module’s outstanding features of interest are:

  • Variable?width lookbehind, a feature which is quite rare in regex engines and very frustrating not to have when you really want it. This may well be the most frequently requested feature in regexes.
  • Backwards searching so you don’t have to reverse your string yourself first.
  • Scoped ismx?type options, so that (?i:foo) only casefolds for foo, not overall, or (?-i:foo) to turn it off just on foo. This is how Perl works (or can).
  • Fuzzy matching based on edit?distance (which Udi Manber’s agrep and glimpse also have)
  • Implicit shortest?to?longest sorted named lists via L<list> interpolation
  • Metacharacters that specifically match only the start or only the end of a word rather than either side (m, M)
  • Support for all Unicode line separators (Java can do this, as can Perl albeit somewhat begrudgingly with R per RL1.6.
  • Full set operations — union, intersection, difference, and symmetric difference — on bracketed character classes per RL1.3, which is much easier than getting at it in Perl.
  • Allows for repeated capture groups like (w+s+)+ where you can get all separate matches of the first group not just its last match. (I believe C# might also do this.)
  • A more straightforward way to get at overlapping matches than sneaky capture groups in lookaheads.
  • Start and end positions for all groups for later slicing/substring operations, much like Perl’s @+ and @- arrays.
  • The branch?reset operator via (?|...|...|...|) to reset group numbering in each branch the way it works in Perl.
  • Can be configured to have your coffee waiting for you in the morning.
  • Support for the more sophisticated word boundaries from RL2.3.
  • Assumes Unicode strings by default, and fully supports RL1.2a so that w, b, s, and such work on Unicode.
  • Supports X for graphemes.
  • Supports the G continuation point assertion.
  • Works correctly for 64?bit builds (re only has 32?bit indices).
  • Supports multithreading.

Ok, that’s enough hype. :)

Yet Another Fine Alternate Regex Engine

One final alternative that is worth looking at if you are a regex geek is the Python library bindings to Russ Cox’s awesome RE2 library. It also supports Unicode natively, including simple char?based casefolding, and unlike re it notably provides for both the Unicode General Category and the Unicode Script character properties, which are the two key properties you most often need for the simpler kinds of Unicode processing.

Although RE2 misses out on a few Unicode features like N{...} named character support found in ICU, Perl, and Python, it has extremely serious computational advantages that make it the regex engine of choice whenever you’re concern with starvation?based denial?of?service attacks through regexes in web queries and such. It manages this by forbidding backreferences, which cause a regex to stop being regular and risk super?exponential explosions in time and space.

Library bindings for RE2 are available not just for C/C++ and Python, but also for Perl and most especially for Go, where it is slated to very shortly replace the standard regex library there.

Monday, June 21, 2021
 
SJain
answered 5 Months ago
92

There's a good tutorial on rebuilding the RPM for pcre here.

If you scroll down to "Updated RPM file for..." you'll find some pre-built RPM's if you just want it to work (remember to restart Apache after you're done, not just a graceful reload).

The tl;dr version is: recompile pcre with --enable-utf8 and --enable-unicode-properties

Thursday, July 29, 2021
 
Floris
answered 3 Months ago
92

This will get you started: jsFiddle example - look below for a better method.

Basically, vertical-align:middle and display:inline-block are used on both the p and the img elements for centering.

HTML

<div class="element">
    <img src="http://placehold.it/150x150"/>
    <p>Lorem Ipsum is simply dummy text </p>
</div>

CSS

.element {
    background:rgb(134, 226, 255);
    margin:10px;
}
p {
    display:inline-block;
    margin:0px;
    width:70%;
    background:white;
    vertical-align:middle;
}
img {
    display:inline-block;
    vertical-align:middle;
}

Here is better approach using display:table/display:table-cell Same HTML..

jsFiddle example - semi-responsive... Other jsFiddle example - responsive img elements..

CSS

.element {
    width:100%;
    display:table;
    background:rgb(134, 226, 255);
    margin:10px 0px;
    padding:10px;
}
p {
    display:table-cell;
    height:100%;
    vertical-align:middle;
    background:white;
}
img {
    display:table-cell;
    width:100%;
    height:auto;
}

Yet another update using media queries

You could obviously use whatever breakpoints you want. I use 480px, as this is just for example purposes. Try resizing the window. jsFiddle example

CSS

@media only screen and (min-width: 480px) {
.element {
    width:100%;
    display:table;
    background:rgb(134, 226, 255);
    margin:10px 0px;
    padding:10px;
    box-sizing:border-box;
    -moz-box-sizing:border-box;
    -webkit-box-sizing:border-box;
}
p {
    display:table-cell;
    height:100%;
    vertical-align:middle;
    background:white;
}
img {
    display:table-cell;
    width:100%;
    height:auto;
}
}
@media only screen and (max-width: 479px) {
.element {
    width:100%;
    background:rgb(134, 226, 255);
    margin:10px 0px;
    padding:10px;
    box-sizing:border-box;
    -moz-box-sizing:border-box;
    -webkit-box-sizing:border-box;
}
p {
    background:white;
}
img {
    width:50%;
    margin:0px auto;
    display:block;
    height:auto;
}
}
Thursday, August 12, 2021
 
mnagel
answered 3 Months ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :
 
Share